Approximation as a Property of a Kernel
An RKHS can impose strong geometric control on its functions, but the space may also be rich enough to approximate a wide range of targets. These are different properties. The RKHS norm measures the size of a function within the space; universality asks whether functions in the space can approximate every continuous target on a specified domain.
The domain and the approximation criterion matter. In this tutorial, the domain is compact, the targets are continuous real-valued functions, and approximation is measured by the largest absolute error over the entire domain. This is uniform approximation, not approximation on average under a probability distribution.
For \(h\in\mathcal{H}_k\), the reproducing property gives \(h(x)=\langle h,k(\cdot,x)\rangle_{\mathcal{H}_k}\). In particular, $$ |h(x)-h(y)|\leq \|h\|_{\mathcal{H}_k}\,\|k(\cdot,x)-k(\cdot,y)\|_{\mathcal{H}_k}. $$ The squared norm on the right is \(k(x,x)+k(y,y)-2k(x,y)\), which tends to zero as \(y\) tends to \(x\) when \(k\) is continuous. Thus RKHS functions are continuous in this setting, so it makes sense to ask whether they are dense in \(C(X)\). Universality concerns the set of functions available for approximation, not a bound on the RKHS norms of approximating functions.
Gaussian Kernels on Compact Euclidean Domains
For \(\sigma>0\), the Gaussian kernel on \(\mathbb{R}^d\) is $$ k_\sigma(x,y)=\exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right). $$ It is continuous and positive definite. If \(X\) is a compact subset of \(\mathbb{R}^d\), its restriction to \(X\) is universal. The key is to express its kernel sections using monomials and then apply the Stone–Weierstrass theorem.
For a multi-index \(\alpha=(\alpha_1,\ldots,\alpha_d)\) of nonnegative integers, write \(|\alpha|=\sum_{j=1}^d\alpha_j\), \(\alpha!=\prod_{j=1}^d\alpha_j!\), and \(x^\alpha=\prod_{j=1}^d x_j^{\alpha_j}\). Expanding the exponential gives $$ k_\sigma(x,y) =\exp\left(-\frac{\|x\|^2}{2\sigma^2}\right) \exp\left(-\frac{\|y\|^2}{2\sigma^2}\right) \sum_{\alpha}\frac{x^\alpha y^\alpha}{\sigma^{2|\alpha|}\alpha!}. $$ Thus the functions $$ \phi_\alpha(x)=\exp\left(-\frac{\|x\|^2}{2\sigma^2}\right) \frac{x^\alpha}{\sigma^{|\alpha|}\sqrt{\alpha!}} $$ give a feature expansion \(k_\sigma(x,y)=\sum_\alpha\phi_\alpha(x)\phi_\alpha(y)\).
A useful feature-space fact is that each finite linear combination of the coordinate functions \(\phi_\alpha\) belongs to the RKHS. Indeed, the feature map \(\Phi(x)=(\phi_\alpha(x))_\alpha\) takes values in \(\ell^2\), and its inner products reproduce the kernel. For any finitely supported coefficient vector \(w\), the function \(x\mapsto\langle w,\Phi(x)\rangle\) is an RKHS function: project \(w\) onto the closed span of \(\{\Phi(x):x\in X\}\), which leaves all these inner products unchanged. Consequently, \(e^{-\|x\|^2/(2\sigma^2)}p(x)\) belongs to the RKHS for every polynomial \(p\).
Proof. Fix \(f\in C(X)\) and \(\varepsilon>0\). Define the continuous function $$ g(x)=f(x)\exp\left(\frac{\|x\|^2}{2\sigma^2}\right). $$ The real Stone–Weierstrass theorem says that a subalgebra of \(C(X)\) which contains the constants and separates points is dense in \(C(X)\). The restrictions of real polynomials to \(X\) form such an algebra: they contain constants, and coordinate polynomials separate any two distinct points of \(X\). Hence there is a polynomial \(p\) with $$ \sup_{x\in X}|g(x)-p(x)|<\varepsilon. $$ The function \(h(x)=e^{-\|x\|^2/(2\sigma^2)}p(x)\) belongs to the Gaussian RKHS by the feature expansion. Since \(e^{-\|x\|^2/(2\sigma^2)}\leq 1\), $$ \sup_{x\in X}|f(x)-h(x)| =\sup_{x\in X}e^{-\|x\|^2/(2\sigma^2)}|g(x)-p(x)| <\varepsilon. $$ This establishes the required density. \(\square\)
Worked Example: An Explicit Gaussian Approximation to a Constant
Take \(X=[-1,1]\), \(\sigma=1\), and target \(f(x)=1\). Write \(t=x^2/2\), so \(0\leq t\leq 1/2\). The degree-four Taylor polynomial for \(e^t\) gives the RKHS function $$ h_4(x)=e^{-x^2/2}\sum_{j=0}^{4}\frac{(x^2/2)^j}{j!}. $$ It belongs to the RKHS because it is the Gaussian factor multiplied by a polynomial.
Taylor's theorem gives, for \(0\leq t\leq 1/2\), $$ 0\leq e^t-\sum_{j=0}^{4}\frac{t^j}{j!} \leq e^{1/2}\frac{(1/2)^5}{5!}. $$ Multiplying by \(e^{-t}\leq 1\) shows $$ \sup_{x\in[-1,1]}|1-h_4(x)| \leq e^{1/2}\frac{1}{3840} <0.00043. $$ This calculation exhibits a specific RKHS function with a uniform error below \(0.00043\). The general theorem guarantees that a suitable approximation also exists for any continuous target on any compact subset of \(\mathbb{R}^d\).
Why Fixed-Degree Polynomial Kernels Can Fail
Consider the inhomogeneous polynomial kernel \(k(x,y)=(c+x^\mathsf{T}y)^m\), where \(m\) is a fixed nonnegative integer and \(c>0\). Expanding the power shows that its feature coordinates are scaled monomials of degrees at most \(m\). Its RKHS is therefore finite-dimensional; restricting the kernel to a domain cannot increase that dimension. (When \(c=0\), the kernel is homogeneous and its features have degree \(m\), so the dimension is finite as well.)
If \(X\) is an infinite compact Hausdorff space, then \(C(X)\) is infinite-dimensional. One way to see this is to choose arbitrarily many distinct points, separate them by pairwise disjoint neighborhoods, and use continuous functions supported in those neighborhoods to obtain linearly independent functions. Every finite-dimensional subspace of a normed space is closed. A finite-dimensional RKHS on such an \(X\) therefore cannot be dense in \(C(X)\).
Proof. Let \(\mathcal{H}_k\) have finite dimension. It is a finite-dimensional subspace of \(C(X)\), so it is closed in the uniform norm. If it were dense in \(C(X)\), its closure would equal \(C(X)\); because it is already closed, this would imply \(\mathcal{H}_k=C(X)\). That is impossible when \(\mathcal{H}_k\) is finite-dimensional and \(C(X)\) is infinite-dimensional. \(\square\)
Worked Example: A Linear Polynomial Kernel Cannot Approximate a Quadratic
On \(X=[-1,1]\), the kernel \(k(x,y)=1+xy\) has RKHS consisting of affine functions \(h(x)=a+bx\). We can show directly that the target \(f(x)=x^2\) cannot be approximated by these functions with uniform error below \(1/2\).
Suppose \(\sup_{x\in[-1,1]}|x^2-(a+bx)|\leq\varepsilon\). At \(x=0\), this implies \(|a|\leq\varepsilon\). At \(x=1\) and \(x=-1\), the two errors are \(1-a-b\) and \(1-a+b\), each with absolute value at most \(\varepsilon\). Their average is \(1-a\), so \(|1-a|\leq\varepsilon\). Therefore $$ 1=|(1-a)-(-a)|\leq |1-a|+|a|\leq 2\varepsilon, $$ and \(\varepsilon\geq 1/2\). This bound is attained by \(a=1/2,\ b=0\), since \(\sup_{x\in[-1,1]}|x^2-1/2|=1/2\). Thus the best possible uniform error is exactly \(1/2\).
Finite-dimensionality does not by itself rule out universality on a finite domain: if \(X\) has \(q\) points, then \(C(X)\) has dimension \(q\). Universality there depends on whether the RKHS can represent every assignment of \(q\) values.
Worked Example: A Polynomial Kernel That Is Universal on Three Points
Let \(X=\{-1,0,1\}\) and use \(k(x,y)=(1+xy)^2\). Its expansion is $$ k(x,y)=1+2xy+x^2y^2, $$ so its feature functions can be taken as \(1,\sqrt{2}x,x^2\). Their values at the three points form the matrix $$ V= \begin{pmatrix} 1&-\sqrt{2}&1\\ 1&0&0\\ 1&\sqrt{2}&1 \end{pmatrix}. $$ Subtracting the second row from the first and third rows gives a determinant of \(2\sqrt{2}\), which is nonzero. Thus the three feature-value vectors span \(\mathbb{R}^3\).
Every function on \(X\) is specified by a vector of three values. Since \(V\) is invertible, for any such vector there are coefficients \(a,b,c\) such that \(a+b\sqrt{2}x+cx^2\) takes those values at \(-1,0,1\). These feature combinations belong to the RKHS, so it contains every function on this finite domain. The kernel is universal on \(X\), despite being finite-dimensional.
Interpreting Universality Correctly
Universality is useful when the aim is to avoid restricting approximation to a fixed finite list of basis functions. For Gaussian kernels on compact Euclidean domains, the theorem guarantees that the RKHS can approximate any continuous target uniformly, regardless of whether the target itself belongs to the RKHS.
A common mistake is to read “universal” as saying that every continuous function is an RKHS member, or that its approximation can be achieved with a uniformly bounded RKHS norm. Neither follows from density. Density only promises, for each positive error tolerance, the existence of some approximant in the RKHS. The norms of a sequence of increasingly accurate approximants may grow without bound.
Universality also depends on the domain and the notion of approximation. The Gaussian result proved here is for compact subsets of \(\mathbb{R}^d\) and uniform approximation. It does not, by itself, make a claim about approximation on an unbounded domain or about approximation measured in a particular distribution's average error. Always specify the space of target functions and the norm in which density is being asserted.
Check Your Understanding
Check that you can apply the definitions and distinguish the domain-dependent cases.
- State the definition of universality, including the domain, target class, and approximation norm.
- Why does the Gaussian feature expansion imply that a Gaussian factor times any polynomial belongs to the RKHS?
- In the Gaussian universality proof, why is the function \(g(x)=f(x)e^{\|x\|^2/(2\sigma^2)}\) continuous?
- Why does finite dimensionality rule out universality on an infinite compact domain, but not necessarily on a finite one?
- For \(k(x,y)=1+xy\) on \([-1,1]\), what is the best uniform approximation error for \(x^2\), and how can it be achieved?