Characteristic Kernels on Groups and Semigroups

Kenji Fukumizu Institute of Statistical Mathematics 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569 Japan fukumizu@ism.ac.jp Arthur Gretton MPI for Biological Cybernetics ¨ Spemannstraße 38, 72076 Tubingen, Germany arthur.gretton@tuebingen.mpg.de

Bharath Sriperumbudur Department of ECE, UC San Diego / MPI for Biological Cybernetics bharathsv@ucsd.edu ¨ Bernhard Scholkopf MPI for Biological Cybernetics bs@tuebingen.mpg.de

Abstract
Embeddings of random variables in reproducing kernel Hilbert spaces (RKHSs) may be used to conduct statistical inference based on higher order moments. For sufficiently rich (characteristic) RKHSs, each probability distribution has a unique embedding, allowing all statistical properties of the distribution to be taken into consideration. Necessary and sufficient conditions for an RKHS to be characteristic exist for Rn . In the present work, conditions are established for an RKHS to be characteristic on groups and semigroups. Illustrative examples are provided, including characteristic kernels on periodic domains, rotation matrices, and Rn . +

1 Introduction
Recent studies have shown that mapping random variables into a suitable reproducing kernel Hilbert space (RKHS) gives a powerful and straightforward method of dealing with higher-order statistics of the variables. For sufficiently rich RKHSs, it becomes possible to test whether two samples are from the same distribution, using the difference in their RKHS mappings [8]; as well as testing independence and conditional independence [6, 9]. It is also useful to optimize over kernel mappings on distributions, for instance to find the most predictive subspace in regression [5], or for ICA [1]. Key to the above work is the notion of a characteristic kernel, as introduced in [5, 6]: it gives an RKHS for which probabilities have unique images (i.e., the mapping is injective). Such RKHSs are sufficiently rich in the sense required above. Universal kernels on compact metric spaces [16] are characteristic [8], as are Gaussian and Laplace kernels on Rn [6]. Recently, it has been shown [14] that a continuous shift-invariant R-valued positive definite kernel on Rn is characteristic if and only if the support of its Fourier transform is the entire Rn . This completely determines the set of characteristic ones in the convex cone of continuous shift-invariant positive definite kernels on Rn . One of the chief advantages of kernel methods is that they allow us to deal straightforwardly with complex domains, through use of a kernel function to determine the similarity between objects in these domains [13]. A question that naturally arises is whether characteristic kernels can be defined on spaces besides Rn . Several such domains constitute topological groups/semigroups, and our focus is on kernels defined by their algebraic structure. Broadly speaking, our approach is based on extensions of Fourier analysis to groups and semigroups, where we apply appropriate extensions of Bochner's theorem to obtain the required conditions on the kernel. The most immediate generalization of the results in [14] is to locally compact Abelian groups, of which (Rn , +) is one example. Thus, in Section 2 we provide review of characteristic kernels on (Rn , +) from this viewpoint. In Section 3 we derive necessary and sufficient conditions for kernels 1


on locally compact Abelian groups to be characteristic. Besides (Rn , +), such groups include [0, 1]n with periodic boundary conditions [13, Section 4.4.4]. We next address non-Abelian compact groups in Section 4, for which we obtain a sufficient condition for a characteristic kernel. We illustrate with the example of S O(3), which describes rotations in R3 , and is used in fields such as geophysics [10] and robotics [15]. Finally, in Section 5, we consider the Abelian semigroup (Rn , +), where + R+ = [0, ). This semigroup has many practical applications, including expressions of nonnegative measures or frequency on n points [3]. Note that in all cases, we provide specific examples of characteristic kernels to illustrate the properties required.

2 Preliminaries: Characteristic kernels and shift-invariant kernels
Let X be a random variable taking values on a measurable space (, B ), and H be a RKHS defined k (X, X )] < . The mean element mX of X is by a measurable kernel k on  such that E [ defined by the element in H such that mX , f H = E [f (X )] (f  H) (See [6, 7]). By plugging f = k (·, y ) in the definition, the explicit functional form of mX is given by mX (y ) = E [k (y , X )]. A bounded measurable kernel k on  is called characteristic if {P : probability on (, B)}  H, P  mP = EX P [k (·, X )] (1) is injective ([5, 6]). Therefore, by definition, a characteristic kernel uniquely determines a probability by its mean element. This property is important in making inference on properties of distributions. It guarantees, for example, that M M D = mX - mY H is a (strict) distance on the space of probabilities on  [8]. The following result provides the necessary and sufficient condition for a kernel to be characteristic and shows its associated RKHS to be a rich function class. Lemma 1. Let (, B) be a measurable space, k be a measurable positive definite kernel on , and H be the associated RKHS. Then, k is characteristic if and only if H + R (direct sum of the two RKHS's) is dense in L2 (P ) for every probability P on (, B). Proof. The "if" part is shown if [6, Lemma 1]. f uppose H + R is not dense in L2 (P ). Then, there n S is f = 0 in L2 (P ) such that dP = 0 and dP = 0 for all   H. Let c = 1/ f L1 (P ) and dek ne Q1 = c|f |P ank Q2 = c(|f | - f )P .fThey are probabilities and Q1 = Q2 by f = 0. Since fi d (y , x)dQ1 (x) - (y , x)dQ2 (x) = c (x)k (y , x)dP (x) = 0, k is not characteristic. The above lemma and Theorem 3 of [6] imply that characteristic kernels give a criterion of (conditional) independence through (conditional) covariance on RKHS, which enables statistical tests of independence with kernels [6]. This explains also the practical importance of characteristic kernels. The following result shows that the characteristic property is invariant under some conformal mappings introduced in [17] and provides a construction to generate new characteristic kernels. Lemma 2. Let  be a topological space with Borel  -field, k be a measurable positive definite  kernel on  such that k (·, y )dµ(y ) = 0 means µ = 0 for a finite Borel measure µ, and f :   C be a bounded continuous function such that f (x) > 0 for all x   and k (x, x)|f (x)|2 is bounded. ~ Then, the kernel k (x, y ) = f (x)k (x, y )f (y ) is characteristic. ~ ~ Prk of. Let P and Q be Borel probabilities such that k (·, x)dP (x) = k (·, x)dQ(x). We have o (·, x)f (x)d(P - Q)(x) = 0, which means f P = f Q. We have P = Q by the positivity and continuity of f . We will focus on spaces with algebraic structure for better description of characteristic kernels. Let G be a group. A function  : G  C is called positive definite if k (x, y ) = (y -1 x) is a positive definite kernel. We call this type of positive definite kernels shift-invariant, because k (z x, z y ) = ((z y )-1 z x) = (y -1 x) = k (x, y ) for any z  G.
n There are many examples of shift-invariant positive definite kernels on the additive group Rn : Gaussian RBF kernel k (x, y ) = exp(- x-y 2 / 2 ) and Laplacian kernel k (x, y ) = exp(- i=1 |xi - yi |) are famous ones. In the case of Rn , the following Bochner's theorem is well-known; Theorem 3 (Bochner). Let  : Rn  C be a continuous function.  is positive definite if and only if there is a unique finite non-negative Borel measure  on Rn such that R T (x) = e -1x  d( ). (2)
n

2


Bochner's theorem completely characterizes the set of continuous shift-invariant positive definite kernels on Rn by the Fourier transform. It also implies that the continuous positive definite functions  T form a convex cone with the extreme points given by the Fourier kernels {e -1x  |   Rn }. It is interesting to determine the class of continuous shift-invariant "characteristic" kernels on Rn . [14] gives a complete solution: if supp() = Rn ,1 then (x - y ) is characteristic. In addition, if a continuous positive definite function of the form in Eq. (2) is real-valued and characteristic, then supp() = Rn . The basic idea is the following: since the mean element EP [(y - X )] is equal to the convolution   P , the Fourier transform rewrites the definition of characteristic property as (P - Q) = 0 = P = Q, where denotes the Fourier transform, and we use   P = P . Hence, it is natural to expect that if  is everywhere positive, then (P - Q) must be zero, which means P = Q. We will extend these results to more general algebraic objects, such as groups and semigroups, on which Fourier analysis and Bochner's theorem can be extended.

3 Characteristic kernels on locally compact Abelian groups
It is known that most of the results on Fourier analysis for Rn are extended to any locally compact Abelian (LCA) group, which is an Abelian (i.e. commutative) topological group with the topology Hausdorff and locally compact. The basic terminologies are provided in the supplementary material for readers who are not familiar to them. The group operation is denoted by "+" in Abelian cases. Hereafter, for a LCA group G, we consider only the probability measures included in the set of finite regular measures M (G) (see Supplements) to discuss characteristic property. This slightly restricts the class of measures, but removes only pathological ones. 3.1 Fourier analysis on LCA Group We briefly summarize necessary results to show our main theorems. For the details, see [12, 11]. For a LCA group G, there exists a non-negative regular measure m on G such that m(E + x) = m(E ) for every x  G and every Borel set E in G. This measure is called Haar measure. We use dx to denote the Haar measure of G. With the Haar measure, the integral is shift-invariant, that is, G G f (x + y )dx = f (x)dx (y  G). The space of Lp (G, dx) is simply denoted by Lp (G). A function  : G  C is called a character of G if  (x + y ) =  (x) (y ) and | (x)| = 1. The set of all continuous characters of G forms an Abelian group with the operation (1 2 )(x) = 1 (x)2 (x). By convention, the group operation is denoted by addition "+", instead of multiplication; i.e., (1 + 2 )(x) = 1 (x)2 (x). This group is called the dual group of G, and denoted by G. For any x  G, the function x on G given by x( ) =  (x) (  G) defines a character of G. It is ^ ^ known that G is a LCA group if the weakest topology is introduced so that x is continuous for each ^ x  G. We can therefore consider the dual of G, denoted by G^ and the group homomorphism ^ , G  G^ ^ , x  x. ^ The Pontryagin duality guarantees that this homomorphism is an isomorphism, and homeomorphism, thus G^ can be identified with G. In view of the duality, it is customary to write (x,  ) := ^  (x). We have (-x,  ) = (x, - ) =  (x)-1 = (x,  ), where z is the complex conjugate of z . Let f  L1 (G) and µ  M (G), the Fourier transform of f and µ are respectively defined by G G ^ f ( ) = (-x,  )f (x)dx, µ( ) = ^ (-x,  )dµ(x), (  G).

(3)

1 For a finite regular measure, there is the largest open set U with µ(U ) = 0. The complement of U is called the support of µ, and denoted by supp(µ). See the supplementary material for the detail.

3


Let f  L (G), g  L1 (G), and µ,   M (G). The convolutions are defined respectively by
G G G (g  f )(x) = f (x - y )g (y )dy , (µ  f )(x) = f (x - y )dµ(y ), (µ   )(E ) = E (x + y )dµ(x)d (y ).

g  f is uniformly continuous on G. For any f , g  L1 (G) and µ,   M (G), we have the formula ^^ f  g = f g, µ  f = µf , µ   = µ. (4) ^ Proposition 4. For µ  M (G), the Fourier transform µ is bounded and uniformly continuous. Theorem 5 (Uniqueness theorem). If µ  M (G) satisfies µ = 0, then µ = 0. It is known that the dual group of the LCA group Rn is {e -1 x |   Rn }, which can be identified with Rn . The above definition and properties of Fourier transform for LCA groups are extension of the ordinary Fourier transform for Rn . Bochner's theorem can be also extended. Theorem 6 (Bochner's theorem. e.g., [12] Section 1.4.3). A continuous function  on G is positive definite if and only if there is a unique non-negative measure   M (G) such that G (x) = (x,  )d( ) (x  G). (5) 3.2 Shift-invariant characteristic kernels on LCA group Based on Bochner's theorem, a sufficient condition of the characteristic property is obtained. Theorem 7. Let  be a continuous positive definite function on a LCA group G given by Eq. (5) with . If supp() = G, then the positive definite kernel k (x, y ) = (x - y ) is characteristic. G Proof. It suffices to prove that if µ  M (G) satisfies µ   = 0 then µ = 0. We have (µ  )(x)dµ(x) = 0. On the other hand, by using Fubini's theorem, G GG GGG (µ  )(x)dµ(x) = (x - y )dµ(y )dµ(x) = (x - y ,  )d( )dµ(y )dµ(x) GG G G = (x,  )dµ(x) (-y ,  )dµ(y )d( ) = |µ()|2 d( ). Since µ is continuous and supp() = G, we have µ = 0, which means µ = 0 by Theorem 5. In real-valued cases, the condition supp() = G is almost necessary. Theorem 8. Let  be a R-valued continuous positive definite function on a LCA group G given by Eq. (5) with . The kernel (x - y ) is characteristic if and only if (i) 0  G is not open and supp() = G, or (ii) 0  G is open and supp()  G - {0}. The case (ii) occurs if G is compact. Proof. It suffices to prove the only if part. Assume k (x, y ) = (x - y ) is characteristic. It is obvious that k is characteristic if and only if so is k (x, y ) + 1. Thus, we can assume 0  supp(). Suppose supp() = G. Since  is real-valued, (-E ) = (E ) for every Borel set E . Thus U := G\supp() is a non-empty open set, with -U = U , and 0  U by assumption. Let 0  U / G × G  G, (1 , 2 )  1 - 2 . Take an open neighborhood W of 0 in G with compact and  : closure such that W   -1 (U - 0 ). Then, (W + (-W ) + 0 )  (W + (-W ) - 0 )  U . Let g = W  -W , where E denotes the indicator function of a set E . i g is continuous, and supp(g )  cl(W + (-W )). Also, g is positive definite, since ,j ci cj g (xi - G G i i xj ) = ci cj W (xi - xj - y )-W (y )dy = W (xi - y )-W (y - xj )dy = ,j ci cj d j G i ,j cj W (xj - y ) y  0. By Bochner's theorem and Pontryagin duality, ci W (xi - y ) there is a non-negative measure µ  M (G) such that G g ( ) = (x,  )dµ(x) (  G). It follows that g ( - 0 ) + g ( + 0 ) = G {(x,  - 0 ) + (x,  + 0 )}dµ(x) = G (x,  )d((0 + 0 )µ)(x).

T

Since supp(g )  cl(W + (-W )), the left hand side is non-zero only in (W + (-W ) + 0 )  (W + (-W ) - 0 )  U , which does not contain 0. Thus, by setting  = 0, we have ((0 + 0 )µ)(G) = 0. 4 (6)


The measure (0 + 0 )µ is real-valued, and non-zero since the function g ( - 0 ) + g ( + 0 ) is not constant zero. Let m = |(0 + 0 )µ|(G), and define the non-negative measures µ1 = |(0 + 0 )µ|/m, µ2 = {|(0 + 0 )µ| - (0 + 0 )µ}/m. Both of µ1 and µ2 are probability measures on G from Eq. (6), and µ1 = µ2 . From Fubini's theorem, G m × ((µ1 - µ2 )  )(x) = (x - y )(0 (y ) + 0 (y ))dµ(y ) G G G = (x,  ) {(y ,  - 0 ) + (y ,  + 0 )}dµ(y )d( ) = (x,  ){g ( - 0 ) + g ( + 0 )}d( ) Since the integrand is zero in supp(), we have (µ1 - µ2 )   = 0, which derives contradiction. The last assertion is obvious, since G is discrete if and only if G is compact [12, Sec. 1.7.3]. Theorems 7 and 8 are generalization of the results in [14]. From Theorem 8, we can see that the characteristic property is stable under the product for shift-invariant kernels. Corollary 9. Let 1 (x - y ) and 2 (x - y ) be R-valued continuous shift-invariant characteristic kernels on a LCA group G. If (i) G is non-compact, or (ii) G is compact and 2 = 0 for any nonzero   G. Then (1 2 )(x - y ) is characteristic. Proof. We show the proof only for (i). Let 1 , 2 be the non-negative measures to give 1 and 2 , respectively, in Eq. (5). By Theorem 8, supp(1 ) = supp(2 ) = G. This means supp(1  2 ) = G. The proof is completed because 1  2 gives a positive definite function 1 2 .
1 Example 1. (Rn , +): As alreadn shown in [6, 14], the Gaussian RBF kernel exp(- 22 x - y 2) y n and Laplacian kernel exp(- i=1 |xi - yi |) are characteristic on R . An example of a positive (x definite kernel that is not characteristic on Rn is sinc(x - y ) = sinx--y) . y

Example 2. ([0, 2 ), +): The addition is made modulo 2 . The dual group is {e -1nx | n  Z}, which is isomorphic to Z. The Fourier transform is equal to the ordinary Fourier expansion. The following are examples of characteristic kernels given by the expression    (x) = n=- an e -1nx , a0  0, an > 0 (n = 0), n=0 an < . (1) a0 =  2 /3, an = 2/n2 (n = 0) (2) a0 = 1/2, an = 1/(1 + n2 ) (n = 0) (3) a0 = 0, an =  /n (n = 0), (|| < 1) (4) an = |n| , (0 <  < 1)
n



 

k1 (x, y ) = ( - (x - y )mod 2 )2 . k2 (x, y ) = cosh( - (x - y )mod 2 ).

 k3 (x, y ) = - log(1 - 2 cos(x - y ) + 2 ).

 k4 (x, y ) = 1/(1 - 2 cos(x - y ) + 2 ) (Poisson kernel).

´ Examples of non-characteristic kernels on [0, 2 ) include cos(x - y ), Fejer, and Dirichlet kernel.

4 Characteristic kernels on compact groups
We discuss non-Abelian cases in this section. Non-Abelian groups include various matrix groups, such as S O(3) = {A  M (3 × 3; R) | AT A = I3 , detA = 1}, which represents rotations in R3 . S O(3) is used in practice as the data space of rotational data, which popularly appear in many fields such as geophysics [10] and robotics [15]. Providing useful positive definite kernels on this class is important in those applications areas. First, we give a brief summary of known results on the Fourier analysis on locally compact and compact groups. See [11, 4] for the details. 4.1 Unitary representation and Fourier analysis Let G be a locally compact group, which may not be Abelian. A unitary representation (T , H ) of G is a group homomorphism T into the group U (H ) of unitary operators on some nonzero Hilbert space H , that is, a map T : G  U (H ) that satisfies T (xy ) = T (x)T (y ) and T (x-1 ) = T (x)-1 = T (x) , and for which x  T (x)u is continuous from G to H for any u  H . For a unitary representation (T , H ) on a locally compact group G, a subspace V in H is called Ginvariant if T (x)V  V for every x  G. A unitary representation (T , H ) is irreducible if there are 5


no closed G-invariant subspace except {0} and H . Unitary representations (T1 , H1 ) and (T2 , H2 ) are said to be equivalent if there is a unitary isomorphism A : H1  H2 such that T1 = A-1 T2 A. The following facts are basic (e.g., [4], Section 3,1, 5.1). Theorem 10. (i) If G is a compact group, every irreducible unitary representation (T , H ) of G is finite dimensional, that is, H is finite dimensional. (ii) If G is an Abelian group, every irreducible unitary representation of G is one dimensional. They are the continuous characters of G. It is possible to extend the Fourier analysis on locally compact non-Abelian groups. Unlike Abelian cases, the Fourier transform by the characters are not possible, but we need to consider unitary representations and operator-valued Fourier transform. Since extending the results of the LCA case to the general cases causes very complicated topology, we focus on compact groups. Also, for simplicity, we assume that G is second countable, i.e., there are countable open basis on G. We define G to be the set of equivalent classes of irreducible unitary representations of a compact group G. The equivalence class of a unitary representation (T , HT ) is denoted by [T ], and the dimensionality of HT by dT . We fix a representative T for every [T ]  G for all. It is known that on a compact group G there is a Haar measure m, which is a left and right invariant non-negative finite measure. We normalize it so that m(G) = 1 and denote it by dx. Let (T , HT ) be a unitary representation. For f  L1 (G) and µ  M (G), the Fourier transform of f and µ are defined by the "operator-valued" functions on G, G G G G -1  -1 f (T ) = f (x)T (x )dx = f (x)T (x) dx, µ(T ) = T (x )dµ(x) = T (x) dµ(x), respectively. These are operators on HT . This is a natural extension of the Fourier transform on LCA groups, where G is the characters serving as the Fourier kernel in view of Theorem 10. We can define the "inverse Fourier transform". Let AT ([T ]  G) be an operator on HT . The series [ (7) T ]G dT Tr[AT T (x)]  [ is said to be absolutely convergent if AT A. It is obvious T ]G dT Tr[|AT |] < , where |A| = that if the above series is absolutely convergent, the convergence is uniform on G. It is known that if G is second countable, G is at most countable, thus the sum is taken over the countable set. Bochner's theorem can be extended to compact groups as follows [11, Section 34.10]. Theorem 11. A continuous function  on a compact group G is positive definite if and only if the Fourier transform (T ) is positive semidefinite, gives an absolutely convergent series Eq. (7), and [  (8) (x) = G dT Tr[ (T )T (x)].
T ]

i [ -1 -1  The proof of "if" part is easy; in fact, G dT Tr[ (T )T (xj xi )] ,j ci cj (xj xi ) = ,j ci cj i T ] j  i [ [   ci T (xi ) (T ) cj T (xj ) ]  0. = ,j ci cj T ] dT Tr[ T ] dT Tr[T (xi ) (T )T (xj ) ] = 4.2 Shift-invariant characteristic kernels on compact groups We have the following sufficient condition of characteristic property for compact groups. Theorem 12. Let  be a positive definite function of the form Eq. (8) on a compact group G. If (T ) is strictly positive definite for every [T ]  G\{1}, the kernel (y -1 x) is characteristic. Proof. Let GP, Q  M (G) be probabilities on G. Define µ = P - Q, and suppose (y -1 x)dµ(y ) = 0. If we take the integral over x with the meaGG [ -1  sure µ, Fubini's theorem shows 0 = x)]dµ(y )dµ(x) = T ] dT Tr[ (T )T (y GG [ [ (T )T (y ) ]dµ(x)dµ(y ) = (T )µ(T ) ]. Since dT > 0 and Tr[T (x) T ] dT T ] dT Tr[µ(T ) G (T ) is strictly positive, µ(T ) = 0 for every [T ]  G, that is, T (x) dµ(x) = O. If we fix an orthonormal basis of HT and express T (x) by the matrix elements Tij (x), we have G Tij (x)dµ(x) = 0 ([T ]  G, i, j = 1, . . . , dT ). 6

i


 The Peter-Weyl Theorem (e.g., [4, Section 5.2]) shows that { dT Tij (x) | [T ]  G, i, j = 1, . . . , dT } is a complete orthonormal basis of L2 (G), which means µ = 0. It is interesting to ask whether Theorem 8 can be extended to compact groups. The same proof does not apply, however, because application of Bochner's theorem to a positive definite function on G is not possible by the lack of duality. Example of SO(3). It is known that S O(3) consists of (Tn , Hn ) (n = 0, 1, 2, . . .), where dTn = 2n + 1. We omit the explicit form of Tn , while it is known (e.g., [4], Section 5.4), but use the character defined by n (x) = Tr[Tn (x)]. It is also known that n is given by n (A) =


sin((2n + 1)) sin 

(n = 0, 1, 2, . . .),

1 where e± -1 (0     ) are the eigenvalues of A, i.e., cos  = 2 Tr[A]. Since plugging (Tn ) = an Id in Eq. (8) derives an n for each term, we see that a sequence {an } such that n=0 Tn  a0  0, an > 0 (n  1), and n=0 an (2n + 1)2 <  defines a characteristic positive definite kernel on S O(3) by

1 sin((2n + 1)) (cos  = Tr[B -1 A], 0     ). sin  2 Some examples are listed below ( is a parameter such that || < 1). k (A, B ) =
n=0 (2n



+ 1)an

(1) an = (2) an =

1 : (2n + 1)4 2n+1 : (2n + 1)2

k1 (A, B ) = k2 (A, B ) =

 1 n sin((2n + 1))  ( - ) = . sin  =0 (2n + 1)3 8 sin 

2 sin  . n 2n+1 sin((2n + 1)) 1 = arctan (2n + 1) sin  2 sin  1 - 2 =0

5 Characteristic kernels on the semigroup Rn +
In this section, we consider kernels on an Abelian semigroup (S, +). In this case, a kernel based on the semigroup structure is defined by k (x, y ) = (x + y ). For an Abelian semigroup (S, +), a semicharacter is defined by a map  : S  C such that (x + y ) = (x)(y ). While extensions of Bochner's theorem are known for semigroups [2], the topology on the set of semicharacters are not as obvious as LCA groups, and the straightforward extension of the results in Section 3 is difficult. We focus only on the Abelian semigroup (Rn , +), where R+ = [0, ). + This semigroup has many practical applications of data analysis including expressions of nonnegative measures or frequency on n points [3]. For Rn , it is easy to see the bounded continuous + n semicharacters are given by { i=1 e-i x | i  0 (i = 1, . . . , n)} [2, Section 4.4]. For Rn , Laplace transform replaces Fourier transform to give Bochner's theorem. + Theorem 13 ([2], Section 4.4). Let  be a bounded continuous function on Rn .  is positive definite + if and only if there exists a unique non-negative measure   M (Rn ) such that + R n (x) = e- i=1 ti xi d(t) (x  Rn ). (9) +
n +

Based on the above theorem, we have the following sufficient condition of characteristic property. Theorem 14. Let  be a positive definite function given by Eq. (9). If supp = Rn , then the + positive definite kernel k (x, y ) = (x + y ) is characteristic. Proof. Let P and Q be probabilities on Rn , and µ = P - Q. Define the Laplace transform by + n R Lµ(t) = n e- i=1 ti xi dµ(x). It is easy to see Lµ is bounded and continuous on Rn . Suppose + +  (x + y )dµ(y ) = 0 for all x  Rn . In exactly the same way as the proof of Theorem 7, we have + LP = LQ. By the uniqueness part of Theorem 13, we conclude P = Q. 7


We show some examples of characteristic kernels on (Rn , +). Let a = (ai )n 1 and b = (bi )n 1 + i= i= (ai  0, bi  0) be non-negative measures on n points. n n (1)  = i=1 t -1 eti ( > 0) : k1 (a, b) = i=1 (ai + bi + )-1 . i (2)  = t-3/2 e- /(4t) ( > 0) : k2 (a, b) = e- i=1 ai +bi .  Since the proof of Theorem 14 shows (x + y )dµ(y ) = 0 means µ = 0 for µ  M (Rn ), Lemma + 2 shows b ( i - n n n ~ k2 (a, b) = exp  ai + bi )/2 - ( i=1 ai + i=1 i )/2 i=1 a - h(a)+h(b) n s also characteristic. The exponent has the form h +b with h(c) = i=1 ci , which 2 2 compares the value of h of the merged measure (a + b)/2 and the average of h(a) and h(b). This type of kernel on non-negative measures is discussed in [3] in connection with semigroup structure.
2

n



6 Conclusions
We have discussed conditions that kernels defined by the algebraic structure of groups and semigroups are characteristic. For locally compact Abelian groups, the continuous shift-invariant Rvalued characteristic kernels are completely determined by the Fourier inverse of positive measures with support equal to the entire dual group. For compact (non-Abelian) groups, we show a sufficient condition of continuous shift-invariant characteristic kernels in terms of the operator-valued Fourier transform. We show a condition for the semigroup Rn . In the advanced theory of harmonic analysis, + Bochner's theorem and Fourier analysis can be extended to more general algebraic structure to some extent. It is interesting to consider generalization of the results in this paper to such general classes. In practical applications of machine learning, we are given a finite sample from a distribution, rather than the distribution itself. In this setting, it becomes important to choose the best possible kernel for inference on this sample. While the characteristic property gives a necessary requirement for RKHS embeddings of distributions to be distinguishable, it does not address optimal kernel choice at finite sample sizes. Theoretical approaches to this problem are the basis for future work.

References
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] F. R. Bach and M. I. Jordan. Kernel independent component analysis. JMLR, 3:1­48, 2002. C. Berg, J. P. R. Christensen, and P. Ressel. Harmonic Analysis on Semigroups. Springer, 1984. M. Cuturi, K. Fukumizu, and J.-P. Vert. Semigroup kernels on measures. JMLR, 6:1169­1198, 2005. B. B. Folland. A course in abstract harmonic analysis. CRC Press, 1995. K. Fukumizu, F. R. Bach, and M. I. Jordan. Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces. JMLR, 5:73­99, 2004. ¨ K. Fukumizu, A. Gretton, X. Sun, and B. Scholkopf. Kernel measures of conditional dependence. Advances in NIPS 20, 489­496. MIT Press, 2008. K. Fukumizu, F. R.Bach, and M. I. Jordan. Kernel dimension reduction in regression. Tech. Report 715, Dept. Statistics, University of California, Berkeley, 2006. ¨ A. Gretton, K. M. Borgwardt, M. Rasch, B. Scholkopf, and A. Smola. A kernel method for the twosample-problem. Advances in NIPS 19. MIT Press, 2007. ¨ A. Gretton, K. Fukumizu, C. H. Teo, L. Song, B. Scholkopf, and A. Smola. A kernel statistical test of independence. Advances in NIPS 20, 585­592. MIT Press, 2008. M. S. Hanna and T. Chang. Fitting smooth histories to rotation data. Journal of Multivariate Analysis, 75:47­61, 2000. E. Hewitt and K. A. Ross. Abstract Harmonic Analysis II. 1970. W. Rudin. Fourier Analysis on Groups. Interscience, 1962. ¨ B. Scholkopf and A.J. Smola. Learning with Kernels. MIT Press. 2002. ¨ B. K. Sriperumbudur, A. Gretton, K. Fukumizu, G. Lanckriet, and B. Scholkopf. Injective Hilbert space embeddings of probability measures. In Proc. COLT 2008, to appear, 2008. O. Stavdahl, A. K. Bondhus, K. Y. Pettersen, and K. E. Malvig. Optimal statistical operators for 3dimensional rotational data: geometric interpretations and application to prosthesis kinematics. Robotica, 23(3):283­292, 2005. I. Steinwart. On the influence of the kernel on the consistency of support vector machines. JMLR, 2:67­ 93, 2001. S. Wu and S-I. Amari. Conformal Transformation of Kernel Functions: A Data-Dependent Way to Improve Support Vector Machine Classifiers. Neural Process. Lett., 15(1):59­67, 2002.

8