Reproducing kernel Hilbert space

A reproducing kernel Hilbert space (RKHS) is a Hilbert space of real- or complex-valued functions defined on some set, with the additional property that the evaluation functional (the map that sends a function to its value at a point) is continuous (bounded). This property ensures the existence of a reproducing kernel — a bivariate function that can be used to compute inner products and reproduce function values. RKHS theory sits at the intersection of functional analysis, approximation theory, and machine learning, providing a rigorous foundation for kernel methods such as support vector machines and Gaussian processes.

1.1 Reproducing kernel

1.1.1 Definition of the kernel

For an RKHS H on X, the reproducing kernel k: X × X -> R (or C) is defined by the property that for each fixed x in X, the function k(·, x) belongs to H and, for all f in H, the reproduction formula f(x) = ⟨f, k(·, x)⟩_H holds. Thus the kernel “reproduces” function values via the inner product. The kernel is unique given the space.

1.1.2 Positive definiteness

A kernel k is called positive definite if for any finite set {x_1, …, x_n} ⊂ X and any scalars {c_1, …, c_n}, the quadratic form Σ_i Σ_j c_i c_j k(x_i, x_j) is non-negative. Every reproducing kernel is positive definite, and conversely, every positive definite kernel gives rise to an RKHS.

1.2 Boundedness of point evaluation

The boundedness of point evaluation is the defining property of an RKHS. By the Riesz representation theorem, continuity of L_x implies there exists a unique function k_x in H such that f(x) = ⟨f, k_x⟩. Defining k(x, y) = k_y(x) yields the reproducing kernel. The boundedness condition is equivalent to the existence of a kernel with the reproducing property.

1.3 Moore–Aronszajn theorem

1.3.1 Existence and uniqueness

The Moore–Aronszajn theorem states that for every positive definite kernel k on a set X, there exists a unique reproducing kernel Hilbert space H_k such that k is its reproducing kernel. The space is constructed as the completion of the linear span of functions {k(·, x): x ∈ X} under the inner product defined by ⟨k(·, x), k(·, y)⟩ = k(x, y).

1.3.2 Construction from a positive definite kernel

Given a positive definite kernel k, one constructs the RKHS as follows: define the vector space V = span{k(·, x): x ∈ X} with the inner product extended linearly from ⟨k(·, x), k(·, y)⟩ = k(x, y). Then H is the completion of V under the induced norm. The resulting space is a Hilbert space of functions on X, and k is its reproducing kernel.

2.1 Sobolev spaces

Sobolev spaces on intervals or domains, when equipped with appropriate inner products, can be RKHSs. For example, the first-order Sobolev space H^1([0,1]) with the norm (∫ f^2 + ∫ (f')^2)^(1/2) is not an RKHS, but a subspace with a weighted inner product can become one.

2.1.1 The Sobolev RKHS of order 1

A classical RKHS is the Sobolev space on [0,1] consisting of absolutely continuous functions with derivative in L^2 and with the inner product ⟨f,g⟩ = f(0)g(0) + ∫_0^1 f'(t)g'(t) dt. Its reproducing kernel is k(x,y) = 1 + min(x,y). This space is widely used in smoothing splines.

2.2 Gaussian (radial basis function) kernels

2.2.1 The Gaussian RKHS

2.2.2 Properties of the Gaussian kernel

The Gaussian kernel is translation-invariant and radial. Its RKHS is isometric to a space of analytic functions via the Fourier transform. The kernel is infinitely differentiable, and the RKHS consists of functions that are real-analytic on R^d. The bandwidth σ controls the smoothness and the effective support of the kernel.

2.3 Polynomial kernels

Polynomial kernels on R^d are defined by k(x,y) = (⟨x,y⟩ + c)^m, where c ≥ 0 and m is a positive integer. The corresponding RKHS is finite-dimensional and consists of polynomials of total degree at most m. The kernel is positive definite if c > 0; for c = 0 it is conditionally positive definite.

2.4 Other common kernels

3.1 Sums and scaling

If k_1 and k_2 are reproducing kernels on the same set X, then any non-negative linear combination a k_1 + b k_2 (with a,b ≥ 0) is also a positive definite kernel, and its RKHS is the direct sum of the component spaces. Scaling by a positive constant changes the norm but not the function space.

3.2 Products and tensor products

The product of two reproducing kernels k_1 (on X) and k_2 (on Y) defines a kernel on X × Y by k((x,y),(x',y')) = k_1(x,x') k_2(y,y'). The resulting RKHS is the tensor product of the two RKHSs. Similarly, pointwise products of kernels on the same set correspond to the intersection of the RKHSs.

3.3 Feature maps and the kernel trick

Every positive definite kernel k can be expressed as an inner product in a feature space: k(x,y) = ⟨φ(x), φ(y)⟩, where φ is a mapping from X to a Hilbert space (feature space). The kernel trick refers to performing computations in that feature space using only kernel evaluations, without explicitly constructing φ.

3.3.1 Explicit feature map construction

For a finite-dimensional RKHS, such as with polynomial kernels, an explicit feature map can be written. For example, for k(x,y) = ⟨x,y⟩^2 on R^2, one can take φ(x) = (x_1^2, √2 x_1 x_2, x_2^2). In the infinite-dimensional case, the feature map is given by φ(x) = k(·, x), the canonical feature map.

4.1 Kernel methods in machine learning

RKHS theory underpins many supervised learning algorithms. The kernel trick allows linear methods to be applied in the feature space implicitly defined by the kernel.

4.1.1 Support vector machines

Support vector machines (SVMs) for classification and regression rely on RKHS kernels. The decision function is of the form f(x) = Σ_i α_i k(x_i, x) + b, where the x_i are training points. The maximum-margin hyperplane in the RKHS leads to convex optimization problems.

4.1.2 Kernel ridge regression

Kernel ridge regression combines an RKHS norm penalty with a squared error loss. The solution is given by the representer theorem: f = Σ_i α_i k(·, x_i), with coefficients obtained from a linear system involving the kernel matrix. The regularization parameter controls the trade-off between data fit and smoothness.

4.2 Probability and statistics

4.2.1 Gaussian processes

A Gaussian process (GP) is a stochastic process whose finite-dimensional distributions are Gaussian. The covariance function of a GP is a positive definite kernel. GPs provide a Bayesian framework for regression and classification, with the RKHS playing the role of the reproducing kernel Hilbert space associated with the covariance kernel.

4.2.2 Reproducing kernels in statistical learning theory

In statistical learning theory, RKHSs are used to derive generalization bounds via the concept of Rademacher complexity. The kernel’s eigen-spectrum influences the sample complexity. Methods such as kernelized empirical risk minimization are studied within this framework.

4.3 Numerical analysis

4.3.1 Approximation theory and regularization

RKHSs provide a natural setting for interpolation and approximation. Given scattered data points, the least-squares approximation in an RKHS yields a solution expressible as a linear combination of kernels. Regularization theory uses RKHS norms to enforce smoothness in inverse problems and ill-posed problems.

5.1 Reproducing kernel Banach spaces

Reproducing kernel Banach spaces (RKBS) generalize RKHSs by replacing the Hilbert space with a Banach space. The evaluation functionals are still continuous, but the norm is not necessarily induced by an inner product. RKBS theory is used in machine learning with non-Hilbertian feature spaces.

5.2 Connections to Mercer’s theorem

Mercer’s theorem provides an eigen-expansion of a continuous positive definite kernel on a compact metric space: k(x,y) = Σ_{i=1}^∞ λ_i e_i(x) e_i(y), where λ_i ≥ 0 and e_i are orthonormal eigenfunctions of the integral operator with kernel k. The RKHS is then isometric to a weighted ℓ^2 space of Fourier coefficients.

5.3 Integral operators and eigenfunction expansions