---
abstract: |
    Kernel methods have been widely applied to machine learning and other questions of approximating an unknown function from its finite sample data. To ensure arbitrary accuracy of such approximation, various denseness conditions are imposed on the selected kernel. This note contributes to the study of universal, characteristic, and $C_0$-universal kernels. We first give simple and direct description of the difference and relation among these three kinds of universalities of kernels. We then focus on translation-invariant and weighted polynomial kernels. A simple and shorter proof of the known characterization of characteristic translation-invariant kernels will be presented. The main purpose of the note is to give a delicate discussion on the universalities of weighted polynomial kernels.

    [**Keywords:**]{} kernel methods, universal kernels, characteristic kernels, density, translation-invariant kernels, weighted polynomial kernels.
author:
- 'Benxun Wang[^1]andHaizhang Zhang[^2]'
title: Universalities of Reproducing Kernels Revisited
---

Introduction
============

Many scientific questions can be mathematically formulated as the learning of an unknown function from its finite sample data. Suppose the unknown target function $f_0$ lives on the input space $X$ and its sample data on the finite sampling points $x_1,x_2,\cdots, x_n\in X$ are available. We human beings learn from experience. By this intuition, a predictor function learned from the finite sample data of $f_0$ on $x_1,x_2,\cdots,x_n$ should be of the form $$\label{section}
\sum_{j=1}^n c_j K(x_j,\cdot),$$ where $c_j$’s are constants and $K$ is a function on $X\times X$ that measures the similarity between inputs from $X$.

The inner product is a natural mathematical tool of measuring similarity. By this consideration, the function $K$ in (\[section\]) is chosen to be of the form $$K(x,y)=\langle \Phi(x),\Phi(y)\rangle_\cW,\ \ x,y\in X$$ where $\Phi$ is a mapping from $X$ to a Hilbert space $\cW$ with inner product $\langle \cdot,\cdot\rangle_\cW$. It has been understood that a function $K$ on $X\times X$ has the above inner product representation if and only if it is a positive-definite function [@Aronszajn], that is, if for all finite points $x_1,x_2,\cdots,x_n\in X$, the matrix $$[K(x_j,x_k)]_{j,k=1}^n$$ is symmetric and positive semi-definite. Moreover, for every positive-definite function $K$ on $X\times X$ there exists a unique Hilbert space, denoted as $\cH_K$, of certain functions on $X$ such that $K(x,\cdot)\in \cH_K$ for all $x\in X$ and $$\label{reproducing}
f(x)=\langle f,K(x,\cdot)\rangle_{\cH_K}\mbox{ for all }f\in\cH_K, \ x\in X.$$ By equation (\[reproducing\]), for each $x\in X$, the point evaluation functional $f\to f(x)$ is a continuous on $\cH_K$. It implies that $\cH_K$ is a [*reproducing kernel Hilbert space*]{} on $X$. For the sake of (\[reproducing\]), positive-definite functions are usually called [*reproducing kernels*]{} in machine learning.

A pleasant coincidence is that the minimizer for all feasible regularization learning algorithms in $\cH_K$ must have the form (\[section\]). Specifically, for any continuous loss function $\cL:\bR^n\to[0,+\infty)$ and non-decreasing regularizer $\phi:[0,+\infty)\to [0,+\infty)$, every minimizer of $$\label{kernelmethod}
\inf_{f\in\cH_K}\cL(f(x_1),f(x_2),\cdots,f(x_n))+\phi(\|f\|_{\cH_K})$$ is of the form (\[section\]). The result is known as the [*representer theorem*]{} in machine learning [@KW]. The hypothesis error in the error estimate of regularization learning algorithms vanishes automatically due to the representer theorem, [@CuckerSmale; @CuckerZhou]. Learning algorithms (\[kernelmethod\]) are the typical [*kernel methods*]{} [@Bishop; @Evgeniou; @Sch] in machine learning. Summarizing the above discussion, we conclude that kernel methods have the natural interpretation of learning from experience and are based on the sound mathematical theory of reproducing kernel Hilbert spaces.

The possibility of approximating the unknown target function from functions of the form (\[section\]) should be first addressed in kernel methods. This denseness question motivates extensive study on universalities of reproducing kernels [@Steinwart1; @Micchelli; @Sriper; @Sriper3; @Sriper1; @CMPY; @Carmeli]. Assume from now on that the input space $X$ is a metric space. We also denote for each compact subset $\cZ\subseteq X$ by $C(\cZ)$ the space of continuous functions on $\cZ$ equipped with the maximum norm $$\|f\|_{C(\cZ)}:=\max\{x\in \cZ:|f(x)|\},$$ and denote by $C_0(X)$ the space of continuous functions on $X$ that vanish at infinity. The study of universal kernels was initiated by Steinwart [@Steinwart1], who posed the question of whether the function in (\[section\]) can approximate any continuous target function arbitrarily well on any compact subset of the input space as the number of sampling points increases. Apparently, this is possible if and only if the linear span of $\{K(x,\cdot):x\in \cZ\}$ is dense in $C(\cZ)$ for all compact $\cZ\subseteq X$. This leads to the definition of universal kernels in [@Micchelli].

\[universalkernel\] Let $X$ be a metric space and $K$ a continuous reproducing kernel on $X$. We call $K$ a [*universal kernel*]{} on $X$ if for every compact subset $\cZ\subseteq X$, $\span\{K(x,\cdot):x\in\cZ\}$ is dense in $C(\cZ)$.

Two other universalities of reproducing kernels appear in the study of reproducing kernel Hilbert space embedding of probability measures [@Sriper; @Sriper3; @Sriper1] and in the construction of reproducing kernel Banach spaces with the $\ell^1$-norm [@Song2011; @Song2013].

\[chaandc0universal\] Let $X$ be a metric space and $K$ a reproducing kernel on $X$ such that $K(x,\cdot)\in C_0(X)$ for all $x\in X$. We call $K$ a [*characteristic kernel*]{} if the mapping from the set of probability Borel measures on $X$ to $\cH_K$ given by $$\bP\to \int_X K(\cdot,t)d\bP(t)$$ is injective. We call $K$ a [*$C_0$-universal kernel*]{} if $\span\{K(x,\cdot):x\in X\}$ is dense in $C_0(X)$.

Characterizations of universal kernels and sufficient conditions for various reproducing kernels to be universal were provided in [@Steinwart1; @Micchelli]. The obtained results have also been established for vector-valued reproducing kernels [@CMPY; @Carmeli]. Characteristic and $C_0$-universal kernels have been extensively studied in [@Sriper; @Sriper3; @Sriper1]. This note endeavors to contribute to the study of universalities of reproducing kernels. Firstly, translation-invariant kernels on Euclidean spaces constitute an important class of reproducing kernels. It has been obtained in [@Sriper] that a continuous translation-invariant kernel is characteristic if and only if its Fourier transform is supported everywhere. As a first contribution of this note, we give a simple and shorter proof of this important result in Section 3. It was pointed both in [@Micchelli] and [@Sriper] that if the support of the Fourier transform of a continuous translation-invariant kernel is a uniqueness set for the set of all the entire functions then the kernel is universal. Our discussion in Section 3 will reveal that this sufficient condition is too strong and is not necessary. Another contribution of this note is that we shall give a detailed discussion on the universalities of polynomial kernels and weighted polynomial kernels, which were barely discussed in [@Micchelli] or [@Sriper; @Sriper3; @Sriper1].

Characterization of Universalites by Borel Measures
===================================================

The purpose of this section is to introduce necessary preliminaries and characterizations of universalities of reproducing kernels for later use.

From now on, $X$ stands for a prescribed metric space and all the function spaces are over the field $\bR$ of real numbers. The Banach space $C_0(X)$ consists of all the continuous functions $f$ on $X$ with the property that for all $\varepsilon>0$, $\{x\in X:|f(x)|\ge \varepsilon\}$ is compact in $X$. The norm on $C_0(X)$ is also the maximum norm, that is, for all $f\in C_0(X)$, $$\|f\|_{C_0(X)}=\max\{|f(x)|:x\in X\}.$$ Denote by $\cB(Y)$ the set of all the finite signed Borel measures on a metric space $Y$. The dual space of $C_0(X)$ is $\cB(X)$, [@Rudin1]. It implies that $T$ is a continuous linear functional on $C_0(X)$ if and only if there exists a Borel measure $\mu\in\cB(X)$ such that $$T(f)=\int_X f(t)d\mu(t),\ \ f\in C_0(X).$$ For each compact subset $\cZ\subseteq X$, the dual of $C(\cZ)$ is also $\cB(\cZ)$.

The following characterization of denseness is a direct corollary of the Hahn-Banach theorem in functional analysis, [@Conway].

\[HahnBanach\] Let $\cB$ be a Banach space and $A\subseteq \cB$. Then the linear span of $A$ is dense in $\cB$ if and only if there does not exist a nontrivial continuous linear functional on $\cB$ that vanishes on $A$.

With the above lemma, one immediately obtains the following characterization of universalities of reproducing kernels.

\[characterizationsthree\] Let $K$ be a reproducing kernel on $X$ such that $K(x,\cdot)\in C_0(X)$ for all $x\in X$. Then the followings hold true:

(i)

:   The kernel $K$ is universal on $X$ if and only if for each compact subset $\cZ\subseteq X$, there does not exist a nonzero Borel measure $\mu\in \cB(\cZ)$ such that $$\int_\cZ K(x,t)d\mu(t)=0\mbox{ for all }x\in \cZ.$$

(ii)

:   The kernel $K$ is $C_0$-universal on $X$ if and only if there does not exist a nonzero Borel measure $\mu\in \cB(X)$ such that $$\int_X K(x,t)d\mu(t)=0\mbox{ for all }x\in X.$$

(iii)

:   The kernel $K$ is characteristic on $X$ if and only if there does not exist a nonzero Borel measure $\mu\in \cB(X)$ such that $\mu(X)=0$ and $$\label{killKinc0}
        \int_X K(x,t)d\mu(t)=0\mbox{ for all }x\in X.$$

Statements (i) and (ii) follow immediately from Lemma \[HahnBanach\]. To confirm (iii), suppose first that there does not exist a nonzero Borel measure $\mu\in \cB(X)$ satisfying $\mu(X)=0$ and equation (\[killKinc0\]). Assume that $\bP,\bQ$ are two probability Borel measures on $X$ such that $$\int_XK(x,t)d\bP(t)-\int_XK(x,t)d\bQ(t)=0\mbox{ for all }x\in X.$$ Then we have $(\bP-\bQ)(X)=1-1=0$ and $$\int_X K(x,t)d(\bP-\bQ)(t)=0\mbox{ for all }x\in X.$$ By our assumption, $\bP-\bQ=0$. Thus, $K$ is characteristic. To see the converse, suppose that $K$ is characteristic and $\mu\in\cB(X)$ satisfies $\mu(X)=0$ and equation (\[killKinc0\]). By the Hahn-Jordan decomposition theorem (see, [@Dudley], Theorem 5.6.1), there exist unique positive Borel measures $\mu^+$ and $\mu^-$ on $X$ such that $\mu=\mu^+-\mu^-$. As $\mu(X)=0$, $\mu^+(X)-\mu^-(X)=0$. Let $C=\mu^+(X)$. Then $$\mu=C(\mathbb{P}-\mathbb{Q}),$$ where $\bP=\mu^+/C$ and $\bQ=\mu^{-}/C$ are two probability Borel measures. By (\[killKinc0\]) and by fact that $K$ is characteristic, $\mu^{+}=\mu^{-}$, yielding that $\mu=0$. The proof is complete.

One can draw a few conclusions on the relations among the three kinds of universalities of reproducing kernels. By (ii) and (iii) in the above theorem, a $C_0$-universal kernel must be characteristic. By Urysohn’s lemma in topology (see, for example, [@Munkres], page 207), every continuous function on a compact subset of the metric space $X$ can be extended to a function in $C_0(X)$. Using this result, one sees from definitions \[universalkernel\] and \[chaandc0universal\] that a $C_0$-universal kernel must also be universal. For more discussion on the relations, see [@Sriper3; @Sriper1].

Translation Invariant Kernels
=============================

Reproducing kernels $K$ on $\bR^d$ that are translation-invariant in the sense that $$K(x,y)=K(x+a,y+a)\mbox{ for all x,y,a}\in \bR^d$$ are of particular importance in machine learning. The celebrated Bochner theorem [@Bochner2] asserts that $K$ is a continuous translation-invariant reproducing kernel on $\bR^d$ if and only if there exists a finite positive Borel measure $\nu$ on $\bR^d$ such that $$\label{bochnercha}
K(x,y)=\int_{\bR^d}e^{i(x-y)^T\xi}d\nu(\xi),\ \ x,y\in\bR^d.$$ Let $K$ be given by (\[bochnercha\]). An important result obtained in the studies [@Sriper] of reproducing kernel Hilbert spaces embedding of probability measure is that $K$ is characteristic if and only if $\supp\nu=\bR^d$. Recall that a point $x_0$ belongs to the support $\supp\nu$ of a positive Borel measure $\nu$ if for any open subset $V\subseteq \bR^d$ that contains $x_0$, $\nu(V)>0$. A main purpose of this section is to give a shorter proof of this result. Moreover, it was both noted in [@Sriper] and [@Micchelli] that when $\supp\nu$ is a uniqueness set for all the entire functions on $\bC^d$ then $K$ is universal. Another objective of this section is to present delicate discussion on the condition for $K$ defined by (\[bochnercha\]) to be universal. In particular, one shall see that the uniqueness condition is not necessary.

To fulfill the two purposes, we shall need basic facts on distributions and the Fourier transform (see, for example, [@Fourier]). Denote by $\cD(\bR^d)$ the space of infinitely differentiable functions on $\bR^d$ with compact support and by $\cS(\bR^d)$ the Schwartz class of rapidly decreasing infinitely differentiable functions on $\bR^d$. There hold the relations that for all $p\in[1,+\infty]$, $$\cD(\bR^d)\subseteq\cS(\bR^d)\subseteq L^p(\bR^d).$$ The dual spaces of $\cD(\bR^d)$ and $\cS(\bR^d)$ are denoted by $\cD'(\bR^d)$ and $\cS'(\bR^d)$, respectively. Elements in $\cD'(\bR^d)$ are called distributions. In particular, those in $\cS'(\bR^d)\subseteq \cD'(\bR^d)$ are called [*tempered distributions*]{}.

The Fourier transform $\hat{f}$ and the inverse Fourier transform $\check{f}$ of $f\in L^1(\bR^d)$ are respectively defined by $$\hat{f}(\xi):=\frac{1}{(2\pi)^{d/2}}\int_{\bR^d}e^{-ix^T\xi}f(x)dx, \ \ \xi\in\bR^d$$ and $\check{f}(\xi)=\hat{f}(-\xi)$, $\xi\in\bR^d$. For all $\varphi\in\cS(\bR^d)$, $\hat{\varphi}\in\cS(\bR^d)$. Furthermore, the Fourier transform is continuous on $\cS(\bR^d)$. This allows us to define the Fourier transform on tempered distributions as follows: $$\hat{T}(\varphi):=T(\hat{\varphi}),\ \ T\in\cS'(\bR^d),\ \varphi\in\cS(\bR^d).$$ The Fourier transform of a tempered distribution remains a tempered distribution. In particular, a signed Borel measure $\mu\in\cB(\bR^d)$ corresponds to a tempered distribution defined by $$\label{distributionmu}
\mu(\varphi):=\int_{\bR^d}\varphi(t)d\mu(t),\ \ \varphi\in\cS(\bR^d).$$ It can be verified by the Fubini theorem that the Fourier transform of this distribution is $$\hat{\mu}(\xi)=\int_{\mathbb{R}^d}e^{-ix^T\xi}d\mu(x),\ \ \xi\in\bR^d,$$ which is bounded and uniformly continuous on $\mathbb{R}^d$.

As a final preparation, we make the following simple observation.

\[reducetosupport\] Let $K$ be a translation-invariant kernel on $\bR^d$ given by (\[bochnercha\]), $\cZ$ a Borel subset in $\bR^d$ and $\mu\in \cB(\cZ)$. Then $$\label{reducetosupporteq1}
\int_\cZ K(x,t)d\mu(t)=0\mbox{ for all }x\in\cZ$$ if and only if $$\label{reducetosupporteq2}
\hat{\mu}(\xi)=\int_{\cZ}e^{-ix^T\xi}d\mu(x)=0\mbox{ for all }\xi\in\supp\nu.$$

Suppose first that (\[reducetosupporteq2\]) holds true. By Fubini’s theorem, we get for all $x\in \cZ$ that $$\int_\cZ K(x,t)d\mu(t)=\int_\cZ \int_{\bR^d}e^{i(x-t)^T\xi}d\nu(\xi)d\mu(t)=\int_{\bR^d}e^{ix^T\xi}d\nu(\xi)\int_\cZ e^{-it^T\xi}d\mu(t)=\int_{\supp\nu}e^{ix^T\xi}\hat{\mu}(\xi)d\nu(\xi)=0.$$ Conversely, suppose that (\[reducetosupporteq1\]) is true. Then for all $x\in\cZ$, $$\int_{\supp\nu}e^{ix^T\xi}\hat{\mu}(\xi)d\nu(\xi)=0.$$ Integrating both sides of the above equation with respect to $d\bar{\mu}(x)$ on $x\in\cZ$ yields by the Fubini theorem that $$\int_{\supp\nu}|\hat{\mu}(\xi)|^2d\nu(\xi)=0,$$ which implies that $\mu$ vanishes everywhere on $\supp\nu$.

\[characterization6\] Let $K$ be the translation-invariant kernel on $\bR^d$ given by (\[bochnercha\]). Then $K$ is characteristic if and only if $\supp\nu=\mathbb{R}^d$.

Suppose first that $\supp\nu=\bR^d$ and suppose that $\mu\in\cB(\bR^d)$ satisfies $$\int_{\bR^d} K(x,t)d\mu(t)=0$$ for all $x\in\bR^d$. Letting $\cZ=\bR^d$ in Lemma \[reducetosupport\] yields that $\hat{\mu}$ is the zero function. Thus, $\mu$ is the zero measure. By (iii) in Theorem \[characterizationsthree\], $K$ is characteristic.

Conversely, suppose that $K$ is characteristic but $\supp\nu$ is a proper subset of $\bR^d$. Then $U:=\mathbb{R}^d\setminus(\supp\nu\cup\{0\})$ is a non-empty open set. There hence exists a nontrivial function $\phi\in \cD(\bR^d)$ with $\supp\phi\subseteq U$. Let $f:=\check{\phi}$, and define a Borel measure $\mu$ on $\mathbb{R}^d$ by $\mu(A)=\int_A f(x)dx$. Clearly, as $\phi\in\cS(\bR^d)$, $f\in \cS(\bR^d)\subseteq L^1(\bR^d)$. Thus, $\mu$ belonds to $\cB(\bR^d)$ and is nontrivial. We hence have $\hat{\mu}=\hat{f}=\phi$, which vanishes on $\supp\nu$ and $0$. The latter implies $\mu(\bR^d)=0$. By Lemma \[reducetosupport\] and (iii) in Theorem \[characterizationsthree\], $K$ is not a characteristic kernel, a contradiction.

By the proof of the sufficiency above and that a $C_0$-universal kernel must be characteristic, $K$ defined by (\[bochnercha\]) is $C_0$-universal if and only if $\supp\nu=\bR^d$. This has also been proved in [@Sriper3].

We next turn to conditions for $K$ given by (\[bochnercha\]) to be a universal kernel. The concept of uniqueness sets is needed.

\[uniqueness\] Let $\bF$ be a class functions on a set $\Omega$. A subset $A\subseteq\Omega$ is called a [*uniqueness set* ]{} for $\bF$ if a function in $\cF$ vanishes on $A$ then it must vanish everywhere on $\Omega$.

Denote by $\cB_c(\bR^d)$ the class of all finite signed Borel measures on $\bR^d$ whose support is compact. Set $$\cF(\cB_c(\bR^d)):=\{\hat{\mu}:\mu\in\cB_c(\bR^d)\}.$$

By Lemma \[reducetosupport\] and (i) in Theorem \[characterizationsthree\], we get the following characterization of universal kernels.

\[lemmauniversal\] Let $K$ be defined by (\[bochnercha\]). Then $K$ is a universal kernel on $\bR^d$ if and only if $\supp\nu$ is a uniqueness set for $\cF(\cB_c(\bR^d))$.

Note that for each $\mu\in\cB_c(\bR^d)$, $\hat{\mu}$ is the restriction on $\bR^d$ of an entire function on $\bC^d$ defined by $$\label{entirefunction}
\hat{\mu}(z):=\int_{\supp\mu} e^{-iz^Tt}d\mu(t),\ \ z\in\bC^d.$$ From this observation, it was immediately concluded in [@Micchelli] and [@Sriper] that if $\supp\nu$ is a uniqueness set for all the entire functions on $\bC^d$ then $K$ is universal. We shall point out that this is unnecessary essentially by the observation that for each compactly-supported signed Borel measure $\mu$ on $\bR^d$, the function (\[entirefunction\]) is not a general entire function but an entire function of exponential type, that is, $$|\hat{\mu}(z)|\le Ce^{\lambda\|z\|},\ \ z\in\bC^d$$ for some positive constants $C,\lambda$. Here, $\|\cdot\|$ is the standard Euclidean norm. For detailed discussion, we introduce the completeness radius of complex exponentials. Set $B_R:=\{x\in\bR^d:\|x\|\le R\}$ for $R\ge 0$. The completeness radius of $\supp\nu$ is defined by $$\cR(\nu):=\sup\{R\ge0: \span\{e^{-ix^Tt}: t\in\supp\nu\}\mbox{ is dense in }C(B_R)\}.$$

\[radius\] The kernel $K$ given by (\[bochnercha\]) is universal if and only if $\cR(\nu)=+\infty$.

The result follows directly from Lemma \[lemmauniversal\].

We next restrict to the one-dimensional case. By the Weierstrass factorization theorem, if $\supp\nu$ has a finite accumulation point then it is a uniqueness set for all the entire functions on $\bC$. Consequently, $K$ is universal in this case. When $\supp\nu$ has no finite accumulation points, reference [@Beurling] provides a deep characterization of the completeness radius of $\supp\nu$ in terms of the Beurling-Malliavin density of the following measure $$\tilde{\nu}(A):=\#\{A\cap\supp\nu\}.$$ Interested readers are referred to [@Beurling] for the detailed definition of the Beurling-Malliavin density, and to [@Redheffer] for an extensive survey on the completeness radius of complex exponentials. We conclude that in the one-dimensional case, $K$ defined by (\[bochnercha\]) is a universal kernel on $\bR$ if and only if $\supp\nu$ has a finite accumulation point or the Beurling-Malliavin density of $\tilde{\nu}$ is infinite.

To end this section, we give an explicit example to show that the uniqueness condition in [@Micchelli; @Sriper] is unnecessary. Let $\supp\nu:=\{\lambda_n:n\in\bN\}$ be free of finite accumulation points. Thus, $\supp\nu$ is not a uniqueness set for all the entire functions on $\bC$.

[@Redheffer] Let $\supp\nu:=\{\lambda_n:n\in\bN\}$. If $$\label{lowerbound}
\limsup_{n\to+\infty}\frac{n}{|\lambda_n|}=+\infty$$ then $\cR(\nu)=+\infty$.

Our example is explicitly given as $$\label{example}
\supp\nu:=\left\{\lambda_n=\frac {n}{\log(n+1)}:n\in
\bN\right\}$$ and $$\nu(\lambda_n)=\frac1{n^2\log(n+1)},\ \ n\in\bN.$$ Clearly, $\supp\nu$ has no finite accumulation points and (\[lowerbound\]) is satisfied. As a result, $K$ is a universal kernel while $\supp\nu$ is not a uniqueness set for all the entire functions on $\bC$. Of course, there exist many other examples. For instance, $\supp\nu=\{n^{\lambda}:n\in\bN\}$ where $0<\lambda<1$.

Polynomial Kernels
==================

In this section, we consider another important class of reproducing kernels–polynomial kernels. They are particular examples of the general Hilbert-Schimidt kernels $$\label{Hilbert}
K(x,y)=\sum_{n\in I}\phi_n(x)\phi_n(y),\ \ (x,y)\in X\times X,$$ where $I$ is a countable index set, $\{\phi_n:n\in I\}\subseteq C(X)$, and the series converges pointwise on $X\times X$. By the Mercer theorem [@Mercer], every continuous kernel is a Hilbert-Schmidt kernel.

We start with conditions ensuring a Hilbert-Schmidt kernel to be universal.

\[Hilbert0\] Let $K$ be a Hilbert-Schmidt kernel given by (\[Hilbert\]). Then the followings hold true:

(i)

:   Suppose the series in (\[Hilbert\]) converges uniformly on every compact subset of $X\times X$. Then for each compact subset $\cZ\subseteq X$ and $\mu\in \cB(\cZ)$, $$\label{Hilbert0eq1}
    \int_\cZ K(x,y)d\mu(y)=0\mbox{ for all } x\in \cZ$$ if and only if $$\label{Hilbert0eq2}
    \int_\cZ \phi_n(y)d\mu(y)=0\mbox{ for all } n\in I.$$

(ii)

:   Suppose there exists a nonnegative sequence $\lambda_n$, $n\in I$ such that $$\label{cohilbertcond}
    |\phi_n(x)|\le \lambda_n\mbox{ for all }x\in X,\ n\in I\mbox{ and }\sum_{n\in I}\lambda_n<+\infty.$$ Then for every $\mu\in\cB(X)$, $$\int_X K(x,y)d\mu(y)=0\mbox{ for all } x\in X$$ if and only if $$\int_X \phi_n(y)d\mu(y)=0\mbox{ for all } n\in I.$$

We prove (i) first. Let $\cZ\subseteq X$ be compact and $\mu\in\cB(\cZ)$. Suppose that (\[Hilbert0eq1\]) holds true. For fixed $x\in \cZ$, by the uniform convergence of the series in (\[Hilbert\]) on $\cZ$, we have $$\label{Hilbert0eq3}
\sum_{n\in I}\phi_n(x)\int_\cZ\phi_n(y)d\mu(y)=\int_\cZ\sum_{n\in I}\phi_n(x)\phi_n(y)d\mu(y)=\int_\cZ K(x,y)d\mu(y)=0.$$ Integrating both sides of the above equation on $x\in \cZ$ with respect to $d\bar{\mu}(x)$ yields $$\biggl|\int_\cZ\phi_n(y)d\mu(y)\biggr|^2=0,\ \ n\in I$$ which proves (\[Hilbert0eq2\]). Conversely, if (\[Hilbert0eq2\]) is true then (\[Hilbert0eq1\]) follows immediately from (\[Hilbert0eq3\]).

Statement (ii) can be proved in a similar way. One only needs to note that condition (\[cohilbertcond\]) ensures that $$\int_X\sum_{n\in I}\phi_n(x)\phi_n(y)d\mu(y)=\sum_{n\in I}\phi_n(x)\int_X \phi_n(y)d\mu(y)$$ and $$\int_X\sum_{n\in I}\phi_n(x)\int_X \phi_n(y)d\mu(y)d\bar{\mu}(x)=\sum_{n\in I}\biggl|\int_X \phi_n(y)d\mu(y)\biggr|^2.$$ The proof is hence complete.

As a direct corollary of the above result, we reprove the following characterizations of universal and $C_0$-universal Hilbert-Schmidt kernels in [@Micchelli] and [@Sriper3].

\[characterizationHilbert\] Let $K$ be given by (\[Hilbert\]). Under the conditions in Lemma \[Hilbert0\], the followings hold true:

(i)

:   $K$ is universal on $X$ if and only if $\span\{\phi_n:n\in I\}$ is dense in $C(\cZ)$ for all compact $\cZ\subseteq X$,

(ii)

:   $K$ is $C_0$-universal on $X$ if and only if $\span\{\phi_n:n\in I\}$ is dense in $C_0(X)$,

(iii)

:   $K$ is characteristic on $X$ if and only if there does not exist a nonzero measure $\mu\in \cB(X)$ such that $\mu(X)=0$ and $$\int_X \phi_n(x)d\mu(x)=0\mbox{ for all }n\in I.$$

In the rest of the section, we restrict our discussion to one-dimensional polynomial kernels. Let $\bZ_+:=\bN\cup\{0\}$ and denote for each sequence $\alpha:=\{\alpha_n\in\bR:n\in\bZ_+\}$ by $\supp\alpha:=\{n\in\bZ_+:\alpha_n\ne0\}$.

Let $\alpha:=\{\alpha_n\ge0:n\in\bZ_+\}$ be such that the convergence radius of $$\sum_{n=0}^\infty\alpha_n z^n,\ \ z\in\bC$$ is infinite. Then the polynomial kernel $$K(x,y):=\sum_{n=0}^\infty \alpha_n x^ny^n,\ \ x,y\in\bR$$ is universal on $\bR$ if and only if $\alpha_0>0$ and $$\sum_{n\in 2\bN\cap\supp\alpha}\frac1n=\sum_{n\in (2\bN+1)\cap\supp\alpha}\frac1n=+\infty.$$

The result follows from the celebrated Müntz theorem [@Pinkus] that for $0=\lambda_0<\lambda_1<\lambda_2<\cdots\to\infty$, $\span\{x^{\lambda_n}:n=0,1,\cdots\}$ is dense in $C[0,1]$ if and only if $$\sum_{n=1}^\infty \frac1{\lambda_n}=+\infty$$ and follows from the observation that each continuous function on $C[-1,1]$ can be factored into the sum of an even continuous function and an odd continuous function.

We remark that the above characterization of universal polynomial kernels can be extended to higher-dimensional spaces by using extensions of the Müntz theorem in multivariables (see, for example, [@Borwein; @Ogawa]).

We next discuss characteristic and $C_0$-universality. As polynomials are unbounded on non-compact domains, we shall consider the weighted polynomial kernels: $$\label{weightedpolynomial}
K_\omega(x,y):=\sum_{n=0}^{+\infty} \alpha_n\omega(x)x^n\omega(y)y^n,\ \ x,y\in\bR,$$ where $\omega$ is a nonnegative continuous function on $\bR$ ensuring that $\omega x^n\in C_0(\bR)$ for all $n\in\bZ_+$. We also assume that there exists a nonnegative sequence $\{\lambda_n:n\in\bZ_+\}$ such that $\sum_{n=0}^\infty \lambda_n$ converges and $$\sqrt{\alpha_n}\omega(x)|x^n|\le \lambda_n\ \ \mbox{ for all }x\in\bR\mbox{ and }n\in\bZ_+.$$ Thus, the weighted polynomial kernel (\[weightedpolynomial\]) satisfies the condition of Lemma \[Hilbert0\]. For $K_\omega$ to be a characteristic or $C_0$-universal kernel, by Proposition \[characterizationHilbert\], $\span\{\omega x^n:n\in\bZ_+\}$ must be dense in $C_0(\bR)$. The necessary and sufficient condition for this density has been established in [@Pollard].

\[Pollard\] The linear span of $\{\omega x^n:n\in\bZ_+\}$ is dense in $C_0(\bR)$ if and only if the following three conditions are satisfied simultaneously:

1.  $\omega(x)\neq0\mbox{ for all }x\in\bR$,

2.  $\int_\mathbb{R}\frac{\log\omega(x)}{1+x^2}dx=-\infty$,

3.  there exists a sequence of polynomials $p_n$ and a constant $C$ such that $\lim_{n\rightarrow\infty}p_n(x)\omega(x)=1$ and $|p_n(x)\omega(x)|\leq C$ for all $x\in\bR$ and $n\in\bZ_+$.

Let $\omega$ satisfy the three conditions in Lemma \[Pollard\]. A typical example is $\omega(x)=e^{-x^2}$ with $p_n$ in condition 3 being $$p_n(x):=\sum_{k=0}^n \frac{x^{2k}}{k!},\ \ x\in\bR.$$ By Proposition \[characterizationHilbert\], $K_\omega$ is both characteristic and $C_0$-universal if $\supp\alpha=\bZ_+$. We show below that this full support condition is not necessary.

Let $K_\omega$ be defined by (\[weightedpolynomial\]) and let $\omega$ be an even function on $\bR$ that is non-increasing on $[0,+\infty)$ and satisfy the three conditions in Lemma \[Pollard\]. If the set $\bZ\setminus \supp\alpha$ is finite then $K_\omega$ is characteristic. If $\alpha_0>0$ and $\bZ\setminus \supp\alpha$ is finite then $K_\omega$ is $C_0$-universal.

Suppose first that $\bZ\setminus \supp\alpha$ is finite. Assume that $\mu\in\cB(\bR)$ satisfies $$\label{killsuppalpha}
\int_\bR \omega(x)x^nd\mu(x)=0\ \ \mbox{ for all }n\in\supp\alpha.$$ Since $\omega$ is even on $\bR$ and non-increasing on $[0,+\infty)$, by the second condition in Lemma \[Pollard\], there exist positive constants $C$ and $A$ such that $$\omega(x)\le e^{-C(1+x^2)},\ \ |x|>A.$$ Therefore, the function $$F(z):=\int_\bR \omega(x)e^{ixz}d\mu(x),\ \ z\in\bC$$ is entire on $\bC$. Equation (\[killsuppalpha\]) implies that $$F^{(n)}(0)=0\ \ \mbox{ for all }n\in\supp\alpha.$$ As $\bZ\setminus \supp\alpha$ is finite, $F$ must be a polynomial. The distribution $$T(\varphi):=\int_\bR \omega(x)\varphi(x)d\mu(x),\ \ \varphi\in\cS(\bR)$$ is hence a finite linear combination of the $\delta$ distribution and its derivatives. In other words, there exists some $m\in\bN$ and constants $c_j\in\bR$, $0\le j\le m$ such that $$\int_\bR \omega(x)\varphi(x)d\mu(x)=\sum_{j=0}^mc_j \varphi^{(j)}(0)\ \ \mbox{ for all }\varphi\in\cS(\bR).$$ It implies that $\supp\mu$ is supported on the singleton $\{0\}$. As $\mu$ is a Borel measure, it must be a multiple of the delta density. When $\mu(\bR)=0$, we get $\mu=0$. When $\alpha_0>0$, we obtain from the first condition in Lemma \[Pollard\] and equation (\[killsuppalpha\]) that $\mu=0$. By Proposition \[characterizationHilbert\], the proof is complete.

[30]{}

N. Aronszajn, Theory of reproducing kernels, [*Trans. Amer. Math. Soc.*]{} **68** (1950), 337–404.

A. Beurling and P. Malliavin, On the closure of characters and the zeros of entire functions, [*Acta. Math.*]{} 118 (1967), 79–93.

C. M. Bishop, [*Neural Networks for Pattern Recognition*]{}, Clarendon Press, Oxford, 1995.

S. Bochner, [*Lectures on Fourier Integrals*]{} with an author’s supplement on monotonic functions, Stieltjes integrals, and harmonic analysis, Annals of Mathematics Studies **42**, Princeton University Press, New Jersey, 1959.

P. Borwein and T. Erdélyi, Generalizations of Müntz’s theorem via a Remez-type inequality for M$\ddot{u}$ntz spaces, [*J. Amer. Math. Soc.*]{} **10** (1997), 327–349.

A. Caponnetto, C. A. Micchelli, M. Pontil, and Y. Ying, Universal multi-task kernels, [*J. Mach. Learn. Res.*]{} **9** (2008), 1615–1646.

C. Carmeli, E. De Vito, A. Toigo, and V. Umanità, Vector valued reproducing kernel Hilbert spaces and universality, [*Analysis and Applications*]{} **8** (2010), 19–61.

J. B. Conway, [*A Course in Functional Anakysis*]{}, 2nd Edition, Springer-Verlag, USA, 1990.

F. Cucker and S. Smale, On the mathematical foundations of learning, [*Bull. Amer. Math. Soc. (N.S.)*]{} **39** (2002), 1–49.

F. Cucker and D. X. Zhou, [*Learning theory: an approximation theory viewpoint*]{}, Cambridge University Press, Cambridge, 2007.

T. Evgeniou, M. Pontil and T. Poggio, Regularization networks and support vector machines, [*Adv. Comput. Math.*]{} **13** (2000), 1–50.

C. Gasquet and P. Witomski, [*Fourier Analysis and Applications*]{}, Springer, New York, 1999.

G. Kimeldorf and G. Wahba, Some results on Tchebycheffian spline functions, [*J. Math. Anal. Appl*]{}. **33** (1971), 82–95.

J. Mercer, Functions of positive and negative type and their connection with the theorey of integral equations, [*Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci.*]{} **209** (1909), 415–446.

C. A. Micchelli, Y. Xu, and H. Zhang, Universal kernels, [*J. Mach. Learn. Res.*]{} **7** (2006), 2651–2667.

J. R. Munkres, [*Topology*]{}, 2nd Edition, Prentice Hall, Upper Saddle River, New Jersey, 2000.

S. Ogawa and K. Kitahara, [An extension of Müntz’s theorems in multivariables]{}, [*Bull. Austral. Math. Soc.*]{} **36** (1987), 375–387.

A. Pinkus, Density in approximation theory, [*Surv. Approx. Theory*]{} **1** (2005), 1–45.

H. Pollard, Solution of Bernstein’s approximation problem, [*Proc. Amer. Math. Soc.*]{} **4** (1953), 869–875.

R. M. Redheffer, Completeness of sets of complex exponentials, [*Adv. Math.*]{} 24 (1977), 1–62.

W. Rudin, [*Real and Complex Analysis*]{}, 3rd Edition, McGraw-Hill, New York, 1987.

B. Schölkopf and A. J. Smola, [*Learning with Kernels*]{}, MIT Press, Cambridge, Mass, 2002.

G. Song and H. Zhang, Reproducing kernel Banach spaces with the $\ell^1$-norm II: Error analysis for regularized least square regression, [*Neural Comput.*]{} **23** (2011), 2713–2729.

G. Song, H. Zhang, and F. J. Hickernell, Reproducing kernel Banach spaces with the $\ell^1$-norm, [*Appl. Comput. Harmon. Anal.*]{} **34** (2013), 96–116.

B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Sch$\ddot{o}$lkopf, and G. R. G. Lanckriet, Hilbert space embeddings and metrics on probability measures, [*J. Mach. Learn. Res.*]{} **11** (2010), 1517–1561.

B. K. Sriperumbudur, K. Fukumizu, and G. R. G. Lanckriet, On the relation between universality, characteristic kernels and RKHS embedding of measures, 13th International Conference on Artificial Intelligence and Statistics, [*JMLR Workshop and Conference Proceedings*]{}, Volume **9**, 2010.

B. K. Sriperumbudur, K. Fukumizu, and G. R. G. Lanckriet, Universality, characteristic Kernels and RKHS embedding of measures, [*J. Mach. Learn. Res.*]{} **12** (2011), 2389–2410.

I. Steinwart, [On the influence of the kernel on the consistency of support vector machines]{}, [*J. Mach. Learn. Res.*]{} **2** (2001), 67–93.

[^1]: School of Mathematics and Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China. E-mail address: [*wangbx3@mail2.sysu.edu.cn*]{}.

[^2]: School of Mathematics and Computational Science and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China. E-mail address: [*zhhaizh2@mail.sysu.edu.cn*]{}. Supported in part by Natural Science Foundation of China under grants 11222103 and 11101438, and by the US Army Research Office.
