45.08.01 · mathematical-statistics / 08-learning-methods

Kernel Methods, Reproducing-Kernel Hilbert Spaces, and the Representer Theorem

shipped3 tiersLean: none

Anchor (Master): Schölkopf & Smola 2002 Learning with Kernels (MIT Press) Ch. 2-4 (kernels, RKHS, representer theorem, regularized risk); Aronszajn 1950 Trans. Amer. Math. Soc. 68 (the Moore-Aronszajn correspondence between PD kernels and RKHS); Wahba 1990 Spline Models for Observational Data (SIAM) Ch. 1 (smoothing splines as an RKHS method, the reproducing-kernel formulation of generalized cross-validation)

Intuition Beginner

Many of the patterns we want to learn are not straight lines. A spam filter, a handwriting reader, a price predictor — each needs a curved, flexible rule, not a flat one. The blunt fix is to invent new features by hand: square a number, multiply two columns together, take a logarithm. Pile up enough invented features and a straight-line method can fit a curved rule in the enlarged space. The problem is that the useful set of invented features can be enormous, even endless, and computing them all is hopeless.

Kernel methods sidestep the whole pile. They rest on one observation: most fitting methods only ever need to know how alike two examples are, not the examples themselves. A kernel is a similarity score — one number for each pair of examples saying how much they resemble each other. If you can compute that score directly, you never have to build the giant feature list. You get the flexibility of a vast feature space at the price of a small similarity table.

The everyday image is a recommendation. To guess whether you will like a film, a good system does not need to list every property of every film; it needs to know which films are similar to ones you already rated. Similarity carries the information. The kernel is that similarity, measured carefully enough that the math behind it stays honest.

The second idea is just as practical. When you fit a flexible rule and ask for the best one that does not overreact to noise, the answer is never some wild abstract function. It is always a simple weighted blend of the similarity scores to your training examples — one weight per example. So even a search over an endless space of curves collapses to finding a handful of numbers.

Visual Beginner

What you might fear you need	What a kernel method actually uses
Every invented feature of every example	A similarity score for each pair of examples
A possibly endless list of coordinates	One number per pair: the kernel value
A weight for each invented feature	One weight per training example
To compute the feature map explicitly	Only the kernel, never the map

The single picture to carry forward: the kernel quietly lifts your data into a roomier space where a flat rule suffices, and it reports back only the distances and angles you need in that space. You enjoy the room without paying to furnish it. And whatever rule you learn there comes back, every time, as a weighted vote among your training examples.

Worked example Beginner

Take three one-dimensional training points: $x_{1} = 0$ , $x_{2} = 1$ , $x_{3} = 2$ . We will use the squared-similarity kernel $K (a, b) = (1 + ab)^{2}$ , a standard choice that secretly corresponds to fitting with the features $1$ , $a$ , and $a^{2}$ .

First, build the similarity table, the $3 \times 3$ Gram matrix. Each entry is $K (x_{i}, x_{j})$ . For example $K (x_{1}, x_{1}) = (1 + 0)^{2} = 1$ , and $K (x_{2}, x_{3}) = (1 + 1 \times 2)^{2} = (3)^{2} = 9$ . Working through all pairs:

K = 1111491925 .

Notice the table is symmetric: the similarity of $x_{2}$ to $x_{3}$ equals the similarity of $x_{3}$ to $x_{2}$ . That symmetry is required of every kernel.

Now check the secret feature claim by hand for one pair. With features $ϕ (a) = (1, a, a^{2})$ , the dot product is $ϕ (a) \cdot ϕ (b) = 1 + ab + a^{2} b^{2}$ . For $a = 1$ , $b = 2$ that is $1 + 2 + 4 = 7$ , but our kernel gave $9$ . They differ because the matching feature map is actually $ϕ (a) = (1, 2 a, a^{2})$ , giving $1 + 2 ab + a^{2} b^{2} = (1 + ab)^{2}$ . For $a = 1$ , $b = 2$ : $1 + 4 + 4 = 9$ . The numbers agree.

What this tells us: the kernel value $9$ and the dot product $9$ are the same number, computed two ways. The kernel route asks for one multiplication and one squaring. The feature route asks you to build the three-coordinate vectors first. For three features the saving is small; for thousands or infinitely many features, the kernel route is the only one that finishes.

Check your understanding Beginner

Formal definition Intermediate+

Let $X$ be a non-empty set (the input space). A symmetric function $K : X \times X \to R$ is a positive-definite kernel if for every finite collection $x_{1}, \dots, x_{n} \in X$ the Gram matrix $K \in R^{n \times n}$ with entries $K_{ij} = K (x_{i}, x_{j})$ is symmetric positive semidefinite, that is $c^{⊤} K c = \sum_{i, j} c_{i} c_{j} K (x_{i}, x_{j}) \geq 0$ for all $c \in R^{n}$ ^{[Schölkopf 2002]}. The kernel trick is the observation that such a $K$ is exactly an inner product of an implicit feature map: there is a Hilbert space $H$ and a map $Φ : X \to H$ with $K (x, x^{'}) = ⟨ Φ (x), Φ (x^{'}) ⟩_{H}$ , so any algorithm written purely in terms of inner products of inputs runs in $H$ while touching only $K$ .

A reproducing-kernel Hilbert space (RKHS) on $X$ is a Hilbert space $H$ of real-valued functions $f : X \to R$ in which, for every $x \in X$ , the evaluation functional $ev_{x} : f \mapsto f (x)$ is bounded (continuous). By the Riesz representation theorem 02.11.08, each $ev_{x}$ is represented by a unique element $K_{x} \in H$ , the representer of evaluation, satisfying the reproducing property

⟨ f, K_{x} ⟩_{H} = f (x) for all f \in H, x \in X .

Writing $K (x, x^{'}) := ⟨ K_{x}, K_{x^{'}} ⟩_{H} = K_{x} (x^{'})$ defines the reproducing kernel of $H$ ; it is symmetric and positive-definite, with feature map $Φ (x) = K_{x}$ . The function $x^{'} \mapsto K (x, x^{'})$ is itself an element of $H$ , namely $K_{x}$ , so the kernel "lives inside" the space it generates.

The correspondence runs both ways. The Moore-Aronszajn theorem states that to every symmetric positive-definite kernel $K$ there corresponds a unique RKHS $H_{K}$ having $K$ as its reproducing kernel ^{[Aronszajn 1950]}. The space is built by taking the linear span $H_{0} = span {K_{x} : x \in X}$ , equipping it with the inner product $⟨ \sum_{i} a_{i} K_{x_{i}}, \sum_{j} b_{j} K_{x_{j}} ⟩ = \sum_{i, j} a_{i} b_{j} K (x_{i}, x_{j})$ (well-defined and positive by positive-definiteness), and completing.

Standard kernels on $X = R^{d}$ include the linear kernel $K (x, x^{'}) = x^{⊤} x^{'}$ (feature map the identity), the polynomial kernel $K (x, x^{'}) = (1 + x^{⊤} x^{'})^{p}$ (feature space all monomials of degree $\leq p$ ), the Gaussian or radial basis function (RBF) kernel $K (x, x^{'}) = exp (- ∥ x - x^{'} ∥^{2} /2 σ^{2})$ (an infinite-dimensional feature space), and the Matérn family interpolating between rough and smooth. Mercer's theorem gives the eigen-picture: for a continuous kernel on a compact domain with measure $μ$ , the integral operator $(T_{K} f) (x) = \int K (x, x^{'}) f (x^{'}) d μ (x^{'})$ is self-adjoint, compact, and positive, so by the spectral theorem 02.11.08 it has eigenfunctions ${e_{j}}$ and eigenvalues $λ_{j} \geq 0$ with the uniformly convergent expansion $K (x, x^{'}) = \sum_{j} λ_{j} e_{j} (x) e_{j} (x^{'})$ , exhibiting the feature map $Φ (x) = (λ_{j} e_{j} (x))_{j}$ explicitly.

Counterexamples to common slips

Symmetry alone is not enough. The function $K (x, x^{'}) = - ∥ x - x^{'} ∥$ is symmetric but its Gram matrices are not positive semidefinite, so it is not a kernel; only the conditional version (positive on the subspace $\sum c_{i} = 0$ ) is admissible, and only after a fix.
Positive-definite kernel does not mean positive-definite Gram matrix. The Gram matrix is required only positive semidefinite; it is singular whenever two inputs coincide or the points are linearly dependent in feature space. The closed forms below use $K + λ I$ precisely to restore invertibility.
The kernel value is not a distance. A large Gaussian kernel value means inputs are close, not far; the induced feature-space distance is $∥ Φ (x) - Φ (x^{'}) ∥^{2} = K (x, x) + K (x^{'}, x^{'}) - 2 K (x, x^{'})$ , which decreases as the kernel grows.
The RKHS norm is not the supremum norm. A small $∥ f ∥_{H}$ controls pointwise values only through $∣ f (x) ∣ = ∣ ⟨ f, K_{x} ⟩ ∣ \leq ∥ f ∥_{H} K (x, x)$ ; functions with bounded sup-norm can have unbounded RKHS norm, which is why the penalty $∥ f ∥_{H}^{2}$ is a genuine smoothness control rather than a size cap.

Key theorem with proof Intermediate+

Theorem (representer theorem — Kimeldorf-Wahba 1971; Schölkopf-Herbrich-Smola 2001). Let $H_{K}$ be the RKHS of a positive-definite kernel $K$ on $X$ , let $(x_{1}, y_{1}), \dots, (x_{n}, y_{n})$ be data, let $L : R^{n} \to R$ be any function of the fitted values $(f (x_{1}), \dots, f (x_{n}))$ , and let $Ω : [0, \infty) \to R$ be strictly increasing. Then every minimizer of the regularized empirical risk

J (f) = L (f (x_{1}), \dots, f (x_{n})) + Ω (∥ f ∥_{H_{K}})

over $f \in H_{K}$ admits a representation $f^{⋆} = \sum_{i = 1}^{n} α_{i} K_{x_{i}}$ , i.e. $f^{⋆} (x) = \sum_{i = 1}^{n} α_{i} K (x_{i}, x)$ for some $α \in R^{n}$ . The proof follows the orthogonal-projection argument of Schölkopf & Smola ^{[Schölkopf 2002]} §4.2 and the original squared-error case of Kimeldorf & Wahba ^{[Kimeldorf 1971]}.

Proof. Let $V = span {K_{x_{1}}, \dots, K_{x_{n}}}$ , a finite-dimensional, hence closed, subspace of $H_{K}$ . By the projection theorem for Hilbert spaces 02.11.08, every $f \in H_{K}$ decomposes uniquely as $f = f_{∥} + f_{⊥}$ with $f_{∥} \in V$ and $f_{⊥} \in V^{⊥}$ . Write $f_{∥} = \sum_{i} α_{i} K_{x_{i}}$ .

The fitted values depend only on the parallel part. By the reproducing property, for each data point $x_{j}$ ,

f (x_{j}) = ⟨ f, K_{x_{j}} ⟩ = ⟨ f_{∥} + f_{⊥}, K_{x_{j}} ⟩ = ⟨ f_{∥}, K_{x_{j}} ⟩ + ⟨ f_{⊥}, K_{x_{j}} ⟩ = f_{∥} (x_{j}),

because $K_{x_{j}} \in V$ and $f_{⊥} ⊥ V$ force $⟨ f_{⊥}, K_{x_{j}} ⟩ = 0$ . Hence $L (f (x_{1}), \dots, f (x_{n})) = L (f_{∥} (x_{1}), \dots, f_{∥} (x_{n}))$ : the loss term is blind to $f_{⊥}$ .

The penalty can only grow with $f_{⊥}$ . By orthogonality and the Pythagorean identity,

∥ f ∥_{H_{K}}^{2} = ∥ f_{∥} ∥_{H_{K}}^{2} + ∥ f_{⊥} ∥_{H_{K}}^{2} \geq ∥ f_{∥} ∥_{H_{K}}^{2},

with equality if and only if $f_{⊥} = 0$ . Since $Ω$ is strictly increasing, $Ω (∥ f ∥) \geq Ω (∥ f_{∥} ∥)$ , again with equality only when $f_{⊥} = 0$ . Combining, $J (f) \geq J (f_{∥})$ , with strict inequality unless $f_{⊥} = 0$ . So any minimizer must have $f_{⊥} = 0$ , hence lies in $V$ and has the claimed finite expansion. When $Ω$ is merely non-decreasing, $f_{∥}$ is a minimizer even if not the unique one. $□$

Bridge. The representer theorem is the foundational reason kernel learning is computationally finite: an optimization over an infinite-dimensional function space reduces to $n$ coefficients $α$ , and the engine is nothing more than orthogonal projection onto the span of the data representers, exactly the Hilbert-space decomposition of 02.11.08. This builds toward the kernel ridge closed form below, where $L$ is squared error and the coefficients solve $(K + λ I) α = y$ , and it appears again in the support vector machine 45.08.02, where $L$ is the hinge loss and the same projection argument forces the solution onto the support vectors. The result is dual to the primal weight-space view of ridge regression 45.06.03: there the unknown is a weight vector $β$ in feature space, here it is a coefficient vector $α$ in data space, and the push-through identity that connects them is exactly the central insight that the two parameterizations describe the same fitted function. Putting these together, the kernel trick supplies the inner products, the reproducing property converts evaluation into an inner product, and the projection theorem guarantees the answer is a finite kernel expansion — three facts that generalise from squared error to any pointwise loss with a monotone norm penalty.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that if $K_{1}, K_{2}$ are positive-definite kernels then so are $K_{1} + K_{2}$ and $c K_{1}$ for $c \geq 0$ , and that the pointwise product $K_{1} K_{2}$ is positive-definite (Schur product theorem).

Hint

For the sum, add the two Gram quadratic forms. For the product, use that the Hadamard product of two PSD matrices is PSD.

Answer

For any $x_{1}, \dots, x_{n}$ and $c \in R^{n}$ , $\sum_{ij} c_{i} c_{j} (K_{1} + K_{2}) (x_{i}, x_{j}) = c^{⊤} K_{1} c + c^{⊤} K_{2} c \geq 0$ , so $K_{1} + K_{2}$ is a kernel; scaling by $c \geq 0$ preserves the sign. For the product, the Gram matrix of $K_{1} K_{2}$ is the Hadamard (entrywise) product $K_{1} \circ K_{2}$ . Writing $K_{1} = \sum_{a} u_{a} u_{a}^{⊤}$ and $K_{2} = \sum_{b} v_{b} v_{b}^{⊤}$ as PSD decompositions, $K_{1} \circ K_{2} = \sum_{a, b} (u_{a} \circ v_{b}) (u_{a} \circ v_{b})^{⊤}$ , a sum of rank-one PSD matrices, hence PSD. So $K_{1} K_{2}$ is positive-definite.

Exercise 4 (medium, symbolic).

Derive the kernel ridge regression coefficients: minimizing $\sum_{i} (y_{i} - f (x_{i}))^{2} + λ ∥ f ∥_{H}^{2}$ over $f \in H_{K}$ , show $α = (K + λ I)^{- 1} y$ where $f = \sum_{i} α_{i} K_{x_{i}}$ .

Hint

Use the representer theorem, then express both the fitted values and the norm in terms of the Gram matrix $K$ .

Answer

By the representer theorem $f = \sum_{i} α_{i} K_{x_{i}}$ , so the fitted vector is $(f (x_{j}))_{j} = K α$ (since $f (x_{j}) = \sum_{i} α_{i} K (x_{i}, x_{j}) = (K α)_{j}$ ), and the norm is $∥ f ∥^{2} = \sum_{ij} α_{i} α_{j} K (x_{i}, x_{j}) = α^{⊤} K α$ . The objective becomes $∥ y - K α ∥^{2} + λ α^{⊤} K α$ . Setting the gradient to zero: $- 2 K (y - K α) + 2 λ K α = 0$ , i.e. $K [(K + λ I) α - y] = 0$ . Solving the bracket, $α = (K + λ I)^{- 1} y$ (valid for $λ > 0$ , where $K + λ I$ is invertible), and $\hat{f} (x) = \sum_{i} α_{i} K (x_{i}, x) = k (x)^{⊤} (K + λ I)^{- 1} y$ with $k (x)_{i} = K (x_{i}, x)$ .

Exercise 7 (hard, short-answer).

Explain why the representer theorem requires the penalty to be a monotone function of the RKHS norm specifically, and give a penalty for which the conclusion can fail.

Hint

The proof needs (a) the loss to depend only on fitted values, and (b) the penalty to be minimized by killing the orthogonal component. Which step breaks if the penalty is not a function of $∥ f ∥$ ?

Answer

The proof has two pillars. First, the loss depends only on the fitted values $f (x_{j}) = ⟨ f, K_{x_{j}} ⟩$ , which lie in the span $V$ , so $f_{⊥}$ is invisible to it — this needs only that the loss is a function of the evaluations, true for any pointwise loss. Second, the penalty must be a non-decreasing function of $∥ f ∥_{H} = ∥ f_{∥} ∥^{2} + ∥ f_{⊥} ∥^{2}$ , so that adding any $f_{⊥}$ strictly increases it; this forces the minimizer to set $f_{⊥} = 0$ . If instead the penalty depended on $f$ through some functional not controlled by the RKHS norm — for instance a penalty that rewards energy in a particular off-span direction, such as $- ⟨ f, g ⟩$ for a fixed $g \in / V$ — then increasing $f_{⊥}$ along $g$ would lower the objective, and the minimizer would leave $V$ . Monotonicity in the RKHS norm is precisely what guarantees the orthogonal complement is dead weight.

Lean formalization Intermediate+

Mathlib does not yet host reproducing-kernel Hilbert spaces, so no module is wired in (lean_status: none). The intended statement of the reproducing property and the representer theorem, once an RKHS structure and an evaluation-functional API exist, would read roughly as follows.

-- Intended shape; not part of the current Babel Bible Lean build.
-- Requires: an RKHS structure with a kernel K and the reproducing property,
-- and Mathlib's orthogonalProjection onto a finite-dimensional subspace.
variable {𝓧 : Type*} {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
  [CompleteSpace H]
variable (K : 𝓧 → H)                 -- the representer x ↦ K_x
variable (eval : 𝓧 → (H →L[ℝ] ℝ))    -- bounded evaluation functionals

-- Reproducing property: ⟪f, K_x⟫ = f(x) = eval x f.
def Reproducing : Prop := ∀ (f : H) (x : 𝓧), inner f (K x) = eval x f

-- Representer theorem: a minimizer of L (fitted values) + Ω ‖f‖ lies in the
-- span of {K (x i)}, because its orthogonal complement raises the norm
-- without changing the fitted values.
theorem representer
    (x : Fin n → 𝓧) (L : (Fin n → ℝ) → ℝ) (Ω : ℝ → ℝ) (hΩ : Monotone Ω)
    (hrep : Reproducing K eval) (f : H)
    (hmin : ∀ g, L (fun i => eval (x i) f) + Ω ‖f‖
                  ≤ L (fun i => eval (x i) g) + Ω ‖g‖) :
    f ∈ Submodule.span ℝ (Set.range (fun i => K (x i))) := by
  sorry

the Mathlib gap analysis records what is missing: a ReproducingKernelHilbertSpace structure with the reproducing property, the Moore-Aronszajn completion construction attaching the unique RKHS to a positive-definite kernel, a positive-definite-kernel typeclass with the Gram-matrix PosSemidef characterisation, and the Mercer eigen-expansion. The representer theorem itself rides on Mathlib's orthogonalProjection and the orthogonal-decomposition API once those objects exist.

Advanced results Master

Kernel ridge regression is the squared-error instance and the cleanest bridge to the weight-space view 45.06.03. With $L (f (x_{1}), \dots, f (x_{n})) = \sum_{i} (y_{i} - f (x_{i}))^{2}$ and $Ω (t) = λ t^{2}$ , the representer theorem gives $\hat{f} = \sum_{i} α_{i} K_{x_{i}}$ with $α = (K + λ I)^{- 1} y$ , so $\hat{f} (x) = k (x)^{⊤} (K + λ I)^{- 1} y$ where $k (x)_{i} = K (x_{i}, x)$ . This is exactly the push-through identity of 45.06.03: in the primal feature space the fit is $Φ (x)^{⊤} (Φ^{⊤} Φ + λ I)^{- 1} Φ^{⊤} y$ , and $(Φ^{⊤} Φ + λ I)^{- 1} Φ^{⊤} = Φ^{⊤} (Φ Φ^{⊤} + λ I)^{- 1}$ turns the $m \times m$ feature-space solve (with $m$ possibly infinite) into the $n \times n$ kernel solve. The kernel trick is the statement that $Φ$ never appears alone, only through $K = Φ Φ^{⊤}$ , so an infinite feature dimension costs nothing.

The Moore-Aronszajn correspondence is sharper than a bare existence claim. The map sending a positive-definite kernel to its RKHS is a bijection onto Hilbert function spaces with continuous evaluations, and it respects structure: the RKHS of $K_{1} + K_{2}$ is the sum space ${f_{1} + f_{2} : f_{i} \in H_{K_{i}}}$ with the infimal-convolution norm, the RKHS of a product kernel is (a quotient of) the tensor product, and the RKHS of a kernel restricted to a subset is the restriction of the functions ^{[Aronszajn 1950]}. Mercer's theorem refines the picture analytically: for a continuous kernel on a compact metric space with a finite Borel measure of full support, the integral operator $T_{K}$ is trace-class with eigenvalues $λ_{1} \geq λ_{2} \geq \dots \to 0$ and orthonormal eigenfunctions $e_{j} \in L^{2} (μ)$ , the kernel expands as $K (x, x^{'}) = \sum_{j} λ_{j} e_{j} (x) e_{j} (x^{'})$ uniformly, and the RKHS is the ellipsoid $H_{K} = {\sum_{j} c_{j} λ_{j} e_{j} : \sum_{j} c_{j}^{2} < \infty}$ with $∥ \sum_{j} a_{j} e_{j} ∥_{H_{K}}^{2} = \sum_{j} a_{j}^{2} / λ_{j}$ . The eigenvalue decay rate is the precise quantification of the kernel's smoothness and governs the generalization rate of kernel methods through the effective dimension $\sum_{j} λ_{j} / (λ_{j} + λ)$ , the kernel analogue of the effective degrees of freedom 45.06.03.

Smoothing splines are the RKHS method that predates the modern kernel vocabulary ^{[Wahba 1990]}. Minimizing $\sum_{i} (y_{i} - f (x_{i}))^{2} + λ \int (f^{''} (t))^{2} d t$ over the Sobolev space $W_{2}^{2}$ is a regularized RKHS problem: the penalty is a squared seminorm whose null space is the linear functions, and the reproducing kernel of the complement is a piecewise-cubic Green's function. The representer theorem (in its seminorm-plus-null-space form) forces the minimizer to be a natural cubic spline with knots exactly at the data points — an $n$ -dimensional solution to an infinite-dimensional variational problem, the original instance of the finite-representation phenomenon. Generalized cross-validation, which selects $λ$ by $GCV (λ) = n^{- 1} ∥ y - S_{λ} y ∥^{2} / (1 - tr (S_{λ}) / n)^{2}$ with smoother matrix $S_{λ} = K (K + λ I)^{- 1}$ , is Wahba's invention and carries over verbatim to kernel ridge regression.

The support vector machine is the same architecture with a different loss 45.08.02. Taking $L$ to be the hinge loss $\sum_{i} max (0, 1 - y_{i} f (x_{i}))$ (with $y_{i} \in {- 1, + 1}$ ) and $Ω (t) = λ t^{2}$ , the representer theorem again forces $\hat{f} = \sum_{i} α_{i} K_{x_{i}}$ , and the Karush-Kuhn-Tucker conditions of the resulting convex program make most $α_{i}$ vanish: the surviving terms are the support vectors, the points on or inside the margin. Sparsity in $α$ is the hinge-loss signature, absent in the dense kernel-ridge solution, and it is the reason SVMs evaluate quickly at test time. The kernel choice is what makes the SVM nonlinear without changing the convex optimization — the kernel trick applied to a maximum-margin classifier.

Synthesis. The foundational reason kernels, RKHS, and the representer theorem cohere into one theory is that a positive-definite kernel is an inner product in disguise, and the reproducing property converts the act of evaluating a function into taking that inner product — so the entire apparatus of Hilbert-space geometry 02.11.08 becomes available for learning. This is exactly the orthogonal-projection decomposition: the data representers $K_{x_{i}}$ span a finite subspace, the loss sees only the projection onto it, and the norm penalty kills the orthogonal complement, which is why an infinite-dimensional search collapses to $n$ coefficients. Putting these together with the Moore-Aronszajn correspondence shows the central insight — that choosing a kernel and choosing a hypothesis space with its smoothness penalty are the same act viewed from two sides, the kernel side computational and the function-space side statistical, joined by the Mercer eigen-expansion that turns the kernel into an explicit feature map. The representer theorem generalises ridge regression 45.06.03 from a fixed finite design to an arbitrary RKHS: kernel ridge is the squared-error case, the smoothing spline is the Sobolev case, and the SVM is the hinge-loss case, each obtained by changing only the loss $L$ while the projection argument and the finite expansion are dual to the same Hilbert-space fact. The bridge is the Gram matrix $K$ : its positive-semidefiniteness certifies the kernel, its regularized inverse $(K + λ I)^{- 1}$ solves the fit, and its eigenvalues quantify the effective dimension that controls generalization.

Full proof set Master

The reproducing property, the Moore-Aronszajn construction, the representer theorem, and the kernel-ridge closed form are established in the Formal definition, Key theorem, and Exercises sections. The remaining Master claims are recorded here.

Proposition 1 (Moore-Aronszajn existence and uniqueness). To every symmetric positive-definite kernel $K$ on $X$ there corresponds a unique Hilbert space $H_{K}$ of functions on $X$ with $K_{x} \in H_{K}$ and the reproducing property $⟨ f, K_{x} ⟩ = f (x)$ for all $f, x$ .

Proof. Existence: on $H_{0} = span {K_{x} : x \in X}$ define $⟨ \sum_{i} a_{i} K_{x_{i}}, \sum_{j} b_{j} K_{x_{j}} ⟩ = \sum_{i, j} a_{i} b_{j} K (x_{i}, x_{j})$ . This is well-defined (independent of representation, since for $f = \sum_{i} a_{i} K_{x_{i}}$ the value $\sum_{i} a_{i} f^{'} (x_{i})$ depends only on $f$ via the reproducing identity on $H_{0}$ ), bilinear, symmetric by symmetry of $K$ , and positive semidefinite by positive-definiteness of $K$ . For definiteness, the bound $∣ f (x) ∣^{2} = ∣ ⟨ f, K_{x} ⟩ ∣^{2} \leq ⟨ f, f ⟩ K (x, x)$ (Cauchy-Schwarz, valid for a positive semidefinite form) shows $⟨ f, f ⟩ = 0 \Rightarrow f \equiv 0$ , so the form is an inner product. Complete $H_{0}$ to a Hilbert space $H_{K}$ ; the same Cauchy-Schwarz bound shows every Cauchy sequence converges pointwise to a function and that evaluation stays continuous, so $H_{K}$ is a function space with the reproducing property extended by continuity. Uniqueness: if $H^{'}$ is another RKHS with kernel $K$ , it contains each $K_{x}$ , contains their span, and the reproducing property fixes the inner product on that span to agree with $H_{K}$ ; closures of the same dense subspace under the same norm coincide, so $H^{'} = H_{K}$ isometrically. $□$

Proposition 2 (kernel trick — feature-map characterisation). A symmetric $K : X \times X \to R$ is positive-definite if and only if there exist a Hilbert space $F$ and a map $Φ : X \to F$ with $K (x, x^{'}) = ⟨ Φ (x), Φ (x^{'}) ⟩_{F}$ .

Proof. ( $\Leftarrow$ ) If $K (x, x^{'}) = ⟨ Φ (x), Φ (x^{'})⟩$ then for any $c$ , $\sum_{ij} c_{i} c_{j} K (x_{i}, x_{j}) = ∥ \sum_{i} c_{i} Φ (x_{i}) ∥^{2} \geq 0$ , and symmetry is inherited from the inner product. ( $\Rightarrow$ ) Take $F = H_{K}$ and $Φ (x) = K_{x}$ ; then $⟨ Φ (x), Φ (x^{'})⟩ = ⟨ K_{x}, K_{x^{'}} ⟩ = K (x, x^{'})$ by definition of the kernel. The canonical feature map is into the RKHS itself, but Proposition 1's Mercer form $Φ (x) = (λ_{j} e_{j} (x))_{j}$ into $ℓ^{2}$ is an alternative when the eigen-expansion converges. $□$

Proposition 3 (kernel ridge equals feature-space ridge). Let $Φ : X \to F$ realise $K$ , $Φ$ the $n \times m$ design with rows $Φ (x_{i})^{⊤}$ (allow $m = \infty$ with the Hilbert-space interpretation). For $λ > 0$ the feature-space ridge fit $\hat{f} (x) = Φ (x)^{⊤} \hat{β}$ , $\hat{β} = (Φ^{⊤} Φ + λ I)^{- 1} Φ^{⊤} y$ , equals the kernel fit $\hat{f} (x) = k (x)^{⊤} (K + λ I)^{- 1} y$ with $K = Φ Φ^{⊤}$ , $k (x)_{i} = K (x_{i}, x)$ .

Proof. The push-through identity $(Φ^{⊤} Φ + λ I_{m})^{- 1} Φ^{⊤} = Φ^{⊤} (Φ Φ^{⊤} + λ I_{n})^{- 1}$ holds because both sides equal $Φ^{⊤} (Φ Φ^{⊤} + λ I_{n})^{- 1}$ after multiplying the identity $Φ^{⊤} (Φ Φ^{⊤} + λ I) = (Φ^{⊤} Φ + λ I) Φ^{⊤}$ on the left and right by the respective inverses (each side of that identity equals $Φ^{⊤} Φ Φ^{⊤} + λ Φ^{⊤}$ ). Hence $\hat{β} = Φ^{⊤} (K + λ I)^{- 1} y$ , and $\hat{f} (x) = Φ (x)^{⊤} \hat{β} = Φ (x)^{⊤} Φ^{⊤} (K + λ I)^{- 1} y$ . Since $(Φ (x)^{⊤} Φ^{⊤})_{i} = ⟨ Φ (x), Φ (x_{i})⟩ = K (x_{i}, x) = k (x)_{i}$ , this is $k (x)^{⊤} (K + λ I)^{- 1} y$ . The proof uses only inner products of feature vectors, so it is valid for $m = \infty$ . $□$

Proposition 4 (Mercer expansion and the RKHS as a weighted ellipsoid). Let $K$ be continuous on a compact $X$ with a finite Borel measure $μ$ of full support. Then $T_{K}$ has eigenpairs $(λ_{j}, e_{j})$ with $λ_{j} \geq 0$ , $\sum_{j} λ_{j} < \infty$ , $K (x, x^{'}) = \sum_{j} λ_{j} e_{j} (x) e_{j} (x^{'})$ uniformly, and $H_{K} = {f = \sum_{j} a_{j} e_{j} : \sum_{j} a_{j}^{2} / λ_{j} < \infty}$ with $∥ f ∥_{H_{K}}^{2} = \sum_{j} a_{j}^{2} / λ_{j}$ (sum over $j$ with $λ_{j} > 0$ ).

Proof. The operator $T_{K}$ on $L^{2} (μ)$ is self-adjoint (by symmetry of $K$ ), positive (by positive-definiteness, $⟨ T_{K} f, f ⟩ = \iint K (x, x^{'}) f (x) f (x^{'}) d μ d μ \geq 0$ as a limit of Gram quadratic forms), and compact (a continuous kernel on a compact domain is Hilbert-Schmidt). The spectral theorem for compact self-adjoint operators 02.11.08 supplies the eigensystem with $λ_{j} \to 0$ ; Mercer's theorem upgrades the $L^{2}$ expansion to uniform convergence using continuity and positivity. Define $Φ (x) = (λ_{j} e_{j} (x))_{j} \in ℓ^{2}$ ; then $⟨ Φ (x), Φ (x^{'})⟩ = \sum_{j} λ_{j} e_{j} (x) e_{j} (x^{'}) = K (x, x^{'})$ , so by Proposition 2 this $Φ$ realises $K$ and its image-space inner product gives the stated RKHS. For $f = \sum_{j} a_{j} e_{j}$ , the reproducing property forces $⟨ f, K_{x} ⟩ = \sum_{j} (a_{j} / λ_{j}) λ_{j} e_{j} (x) = f (x)$ precisely when the inner product is $⟨ \sum a_{j} e_{j}, \sum b_{j} e_{j} ⟩_{H_{K}} = \sum_{j} a_{j} b_{j} / λ_{j}$ , giving the ellipsoid norm. $□$

Connections Master

Ridge regression and shrinkage 45.06.03 is the parent: kernel ridge regression is its kernelized form, obtained by the push-through identity proved here as Proposition 3, and the effective-dimension quantity $\sum_{j} λ_{j} / (λ_{j} + λ)$ that controls kernel generalization is the Mercer-eigenvalue version of the effective degrees of freedom $tr (H_{λ})$ defined there; the Gaussian-prior reading of ridge becomes the Gaussian-process prior whose covariance is the kernel.

Hilbert space 02.11.08 supplies the entire engine: the Riesz representation theorem produces the representer $K_{x}$ of each evaluation functional, the projection theorem yields the orthogonal decomposition $f = f_{∥} + f_{⊥}$ that drives the representer theorem, and the spectral theorem for compact self-adjoint operators produces the Mercer eigen-expansion of Proposition 4.

Support vector machines 45.08.02 are the next unit: the same representer theorem with the hinge loss in place of squared error gives the sparse support-vector expansion, and the kernel trick makes the maximum-margin classifier nonlinear while keeping the optimization convex; this unit supplies the RKHS and representer-theorem foundation that the SVM specializes.

The spectral theorem and functional-analytic operator theory of 02.11.08 reappear through Mercer's theorem, which is the spectral decomposition of the kernel integral operator; the eigenfunction basis is the infinite-dimensional analogue of the singular-vector basis that diagonalizes ridge regression in 45.06.03.

Gaussian processes and Bayesian nonparametrics (forward) make the kernel a prior covariance: the kernel-ridge predictor $k (x)^{⊤} (K + λ I)^{- 1} y$ is exactly the posterior mean of a Gaussian process with covariance $K$ and noise variance $λ$ , so the RKHS norm penalty and the Gaussian-process prior are the same regularizer, paralleling the ridge/Gaussian-prior identification of 45.06.03.

Historical & philosophical context Master

The theory of reproducing kernels was unified by Nachman Aronszajn in his 1950 Transactions of the American Mathematical Society paper ^{[Aronszajn 1950]}, which gave the correspondence between symmetric positive-definite kernels and Hilbert function spaces its definitive form and proved the existence-uniqueness theorem now called Moore-Aronszajn, after E. H. Moore's earlier "positive Hermitian matrices" of the 1930s. James Mercer had established the eigen-expansion of a continuous positive-definite kernel in 1909 in the context of integral equations, well before the Hilbert-space language existed; his theorem became the bridge between the analytic and the feature-space pictures. The kernels themselves had appeared across mathematics — in potential theory as Green's functions, in probability as covariance functions of Gaussian processes, and in the theory of integral equations — long before they were recognized as one object.

The statistical use began with smoothing splines. George Kimeldorf and Grace Wahba proved the representer theorem for squared-error spline-smoothing problems in 1971 ^{[Kimeldorf 1971]}, showing the infinite-dimensional variational problem has a finite-dimensional natural-spline solution, and Wahba's 1990 monograph ^{[Wahba 1990]} developed the reproducing-kernel framework for observational data together with generalized cross-validation. The machine-learning rediscovery came through Bernhard Schölkopf, Alexander Smola, and collaborators in the late 1990s, who recognized the kernel trick as a way to nonlinearize the support vector machine of Vapnik and Cortes and generalized the representer theorem to arbitrary pointwise losses with monotone regularizers; their 2002 monograph Learning with Kernels ^{[Schölkopf 2002]} consolidated the field. Hastie, Tibshirani, and Friedman ^{[Hastie 2009]} placed the RKHS regularization framework, kernel ridge regression, and smoothing splines in a single statistical account in The Elements of Statistical Learning.

Bibliography Master

@article{aronszajn1950reproducing,
  author  = {Aronszajn, Nachman},
  title   = {Theory of Reproducing Kernels},
  journal = {Transactions of the American Mathematical Society},
  volume  = {68},
  number  = {3},
  pages   = {337--404},
  year    = {1950}
}

@article{mercer1909functions,
  author  = {Mercer, James},
  title   = {Functions of Positive and Negative Type, and their Connection with the Theory of Integral Equations},
  journal = {Philosophical Transactions of the Royal Society A},
  volume  = {209},
  pages   = {415--446},
  year    = {1909}
}

@article{kimeldorf1971spline,
  author  = {Kimeldorf, George and Wahba, Grace},
  title   = {Some Results on Tchebycheffian Spline Functions},
  journal = {Journal of Mathematical Analysis and Applications},
  volume  = {33},
  number  = {1},
  pages   = {82--95},
  year    = {1971}
}

@book{wahba1990spline,
  author    = {Wahba, Grace},
  title     = {Spline Models for Observational Data},
  series    = {CBMS-NSF Regional Conference Series in Applied Mathematics},
  volume    = {59},
  publisher = {SIAM},
  year      = {1990}
}

@book{scholkopf2002learning,
  author    = {Sch\"olkopf, Bernhard and Smola, Alexander J.},
  title     = {Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond},
  publisher = {MIT Press},
  year      = {2002}
}

@inproceedings{scholkopf2001generalized,
  author    = {Sch\"olkopf, Bernhard and Herbrich, Ralf and Smola, Alexander J.},
  title     = {A Generalized Representer Theorem},
  booktitle = {Proceedings of the 14th Annual Conference on Computational Learning Theory (COLT)},
  pages     = {416--426},
  year      = {2001}
}

@book{hastie2009elements,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009},
  note      = {Chapter 5 (basis expansions and regularization), §5.8 (RKHS regularization); Chapter 12 (support vector machines)}
}

Prerequisites

45.06.03
02.11.08

Tier anchors

beginner: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) §5.8 and §6.3 (kernels as similarity, the basis-expansion picture); a 'measure how alike two things are, then predict by weighted voting of similar examples' analogy for the kernel trick
intermediate: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e §5.8 (regularization in a reproducing-kernel Hilbert space, the representer theorem, kernel ridge regression); Schölkopf & Smola 2002 Learning with Kernels (MIT Press) Ch. 2 (positive-definite kernels and feature maps) and §4.2 (the representer theorem)
master: Schölkopf & Smola 2002 Learning with Kernels (MIT Press) Ch. 2-4 (kernels, RKHS, representer theorem, regularized risk); Aronszajn 1950 Trans. Amer. Math. Soc. 68 (the Moore-Aronszajn correspondence between PD kernels and RKHS); Wahba 1990 Spline Models for Observational Data (SIAM) Ch. 1 (smoothing splines as an RKHS method, the reproducing-kernel formulation of generalized cross-validation)

References

Hastie, T., Tibshirani, R. & Friedman, J. — The Elements of Statistical Learning (2nd ed.) · Springer, 2009. Ch. 5 (basis expansions and regularization): §5.8 (regularization and reproducing-kernel Hilbert spaces — the penalized functional sum L(y_i, f(x_i)) + lambda ||f||^2_{H_K}, the representer theorem reduction to f(x) = sum alpha_i K(x, x_i), and the kernel ridge / smoothing-spline solution (K + lambda I)^{-1} y); §5.4-5.5 (smoothing splines as the Sobolev-RKHS instance with the second-derivative roughness penalty and the natural-cubic-spline minimizer); Ch. 6 (kernel smoothing methods); Ch. 12 §12.3 (support vector machines via the kernel inner product).
Schölkopf, B. & Smola, A. J. — Learning with Kernels · MIT Press, 2002. Ch. 2 (kernels): positive-definite (Mercer) kernels, the kernel trick as an implicit feature map Phi(x) = K(., x), the Gram matrix and its positive semidefiniteness; the reproducing-kernel Hilbert space construction and the reproducing property <f, K(., x)> = f(x); §4.2 (the representer theorem of Kimeldorf-Wahba generalized to arbitrary monotone regularizers, proved by orthogonal projection onto span{K(., x_i)}); standard kernels (linear, polynomial, Gaussian RBF) and their feature spaces.
Aronszajn, N. — Theory of Reproducing Kernels · Transactions of the American Mathematical Society 68 (3), 337-404 (1950). The Moore-Aronszajn theorem: to every symmetric positive-definite kernel K on a set X there corresponds one and only one Hilbert space of functions on X in which K is the reproducing kernel; the completion-of-the-span construction; the sum and restriction theorems for reproducing kernels.
Wahba, G. — Spline Models for Observational Data · SIAM CBMS-NSF Regional Conference Series 59 (1990). Ch. 1 (the reproducing-kernel framework for smoothing splines: the Sobolev space W_2^m with its reproducing kernel, the penalized least-squares problem with the integrated-squared-mth-derivative penalty, and the finite-dimensional natural-spline solution); the Kimeldorf-Wahba representer theorem and generalized cross-validation for the smoothing parameter.
Kimeldorf, G. & Wahba, G. — Some results on Tchebycheffian spline functions · Journal of Mathematical Analysis and Applications 33 (1), 82-95 (1971). The original representer theorem for squared-error-plus-RKHS-norm problems: the minimizer of a smoothing problem lies in the finite-dimensional span of representers of the evaluation functionals at the data points.

Estimated time

beginner: 25m
intermediate: 55m
master: 90m