RKHS & Kernel Methods

Proof:

We construct \(\mathcal{H}_K\) explicitly in four steps.

Step 1 (pre-Hilbert space). Let \(\mathcal{H}_0 = \operatorname{span}\{K(\cdot, x) : x \in \mathcal{X}\}\) and define a bilinear form on the generators by \(\langle K(\cdot, x), K(\cdot, x') \rangle := K(x, x')\). Symmetry of \(K\) makes this form symmetric. For any finite linear combination \(f = \sum_i a_i K(\cdot, x_i)\), bilinearity forces \(\langle f, f\rangle = \sum_{i,j} a_i a_j K(x_i, x_j) \geq 0\) by the Gram-matrix condition, so the form is positive semi-definite. Well-definedness of the bilinear extension to all of \(\mathcal{H}_0\) is established next. The point to check is that \(\langle f, g\rangle\) does not depend on the chosen finite-sum representations of \(f\) and \(g\).

Step 2 (reproducing property on \(\mathcal{H}_0\), well-definedness, positive definiteness). For \(f = \sum_i a_i K(\cdot, x_i)\), direct computation gives \(\langle f, K(\cdot, x)\rangle = \sum_i a_i K(x_i, x) = f(x)\). Consequently, for any \(g = \sum_j b_j K(\cdot, y_j) \in \mathcal{H}_0\), bilinearity yields \(\langle f, g\rangle = \sum_j b_j f(y_j)\), a value determined entirely by the function \(f\) (not its representation) and the data \((b_j, y_j)\). A symmetric argument in the first slot completes the verification that \(\langle\cdot,\cdot\rangle\) is well-defined on \(\mathcal{H}_0\). The Cauchy-Schwarz inequality then gives \(|f(x)|^2 = |\langle f, K(\cdot, x)\rangle|^2 \leq \langle f, f\rangle \cdot K(x, x)\), so \(\langle f, f\rangle = 0\) forces \(f \equiv 0\). The form is therefore a genuine inner product.

Step 3 (completion as a function space). This is the heart of the theorem. We build the completion of \(\mathcal{H}_0\) directly as a space of functions. Call a sequence \(\{f_n\} \subset \mathcal{H}_0\) that is Cauchy for the inner product of Step 2 an approximating sequence. For each \(x \in \mathcal{X}\), the Cauchy-Schwarz bound from Step 2 gives \(|f_n(x) - f_m(x)| \leq \|f_n - f_m\| \cdot \sqrt{K(x, x)}\), so \(\{f_n(x)\}\) is Cauchy in \(\mathbb{R}\) and converges. Let \(\mathcal{H}_K\) be the set of all pointwise limits \(f(x) = \lim_n f_n(x)\) of approximating sequences. It is a vector space of functions \(\mathcal{X} \to \mathbb{R}\) containing \(\mathcal{H}_0\) (constant sequences).

The key observation is that an approximating sequence \(\{h_n\}\) with \(h_n(x) \to 0\) for every \(x\) satisfies \(\|h_n\| \to 0\). Given \(\varepsilon \gt 0\), choose \(N\) with \(\|h_n - h_m\| \lt \varepsilon\) for \(n, m \geq N\), and fix \(m \geq N\). Writing \(h_m = \sum_i a_i K(\cdot, y_i)\), the reproducing property on \(\mathcal{H}_0\) gives \(\langle h_n, h_m\rangle = \sum_i a_i h_n(y_i) \to 0\) as \(n \to \infty\). Hence \[ \|h_m\|^2 = \langle h_m - h_n, h_m\rangle + \langle h_n, h_m\rangle \leq \varepsilon \|h_m\| + \langle h_n, h_m\rangle \] for every \(n \geq N\). Letting \(n \to \infty\) gives \(\|h_m\|^2 \leq \varepsilon \|h_m\|\), hence \(\|h_m\| \leq \varepsilon\) for every \(m \geq N\).

For \(f, g \in \mathcal{H}_K\) with approximating sequences \(\{f_n\}\) and \(\{g_n\}\), set \(\langle f, g\rangle := \lim_n \langle f_n, g_n\rangle\). The limit exists because Cauchy sequences are bounded and \[ \begin{align*} |\langle f_n, g_n\rangle - \langle f_m, g_m\rangle| &\leq |\langle f_n - f_m, g_n\rangle| + |\langle f_m, g_n - g_m\rangle| \\\\ &\leq \|f_n - f_m\| \|g_n\| + \|f_m\| \|g_n - g_m\|. \end{align*} \] It does not depend on the chosen sequences: two approximating sequences for the same \(f\) differ by an approximating sequence that tends to \(0\) pointwise, hence in norm by the key observation, and the same estimate shows the limit is unchanged. Bilinearity, symmetry, and \(\langle f, f\rangle \geq 0\) pass to the limit, and on \(\mathcal{H}_0\) the new form agrees with that of Step 2. If \(\langle f, f\rangle = 0\), then \(\|f_n\| \to 0\) and \(|f(x)| = \lim_n |f_n(x)| \leq \lim_n \|f_n\| \sqrt{K(x, x)} = 0\) for every \(x\). The form is therefore an inner product on \(\mathcal{H}_K\).

If \(\{f_n\}\) approximates \(f\), then \(\{f_n - f_m\}_n\) approximates \(f - f_m\), so \(\|f - f_m\| = \lim_n \|f_n - f_m\|\), which tends to \(0\) as \(m \to \infty\). Thus every approximating sequence converges in \(\mathcal{H}_K\) to its pointwise limit, and \(\mathcal{H}_0\) is dense in \(\mathcal{H}_K\). For completeness, let \(\{u_k\}\) be Cauchy in \(\mathcal{H}_K\) and choose \(h_k \in \mathcal{H}_0\) with \(\|u_k - h_k\| \lt 1/k\). Since \(\|h_k - h_l\| \leq 1/k + \|u_k - u_l\| + 1/l\), the sequence \(\{h_k\}\) is an approximating sequence, so it has a pointwise limit \(u \in \mathcal{H}_K\) with \(\|u - h_k\| \to 0\), and \(\|u - u_k\| \leq \|u - h_k\| + 1/k \to 0\). Hence \(\mathcal{H}_K\) is a Hilbert space whose elements are bona fide functions on \(\mathcal{X}\).

Step 4 (reproducing property on \(\mathcal{H}_K\), uniqueness). Each \(K(\cdot, x)\) lies in \(\mathcal{H}_0 \subseteq \mathcal{H}_K\). For \(f \in \mathcal{H}_K\) with approximating sequence \(\{f_n\}\), the definition of the inner product and Step 2 give \[ \begin{align*} \langle f, K(\cdot, x)\rangle &= \lim_{n \to \infty} \langle f_n, K(\cdot, x)\rangle \\\\ &= \lim_{n \to \infty} f_n(x) = f(x). \end{align*} \] Hence \(|f(x)| \leq \|f\| \sqrt{K(x, x)}\), so every point evaluation \(\delta_x\) is bounded, and \(K(\cdot, x)\) represents \(\delta_x\). Thus \(K_x = K(\cdot, x)\) and \(K\) is the reproducing kernel of \(\mathcal{H}_K\) in the sense of the Definition. Uniqueness of the reproducing kernel follows from the Riesz Representation Theorem. Each \(\delta_x\) determines its representative \(K_x\) uniquely.

For uniqueness of \(\mathcal{H}_K\) itself, let \(\tilde{\mathcal{H}}\) be any Hilbert space of functions on \(\mathcal{X}\) with reproducing kernel \(K\). It contains every \(K(\cdot, x)\), hence \(\mathcal{H}_0\), and the reproducing property forces its inner product to agree with that of Step 2 on \(\mathcal{H}_0\). Moreover \(\mathcal{H}_0\) is dense in \(\tilde{\mathcal{H}}\): a \(w \in \tilde{\mathcal{H}}\) orthogonal to \(\mathcal{H}_0\) satisfies \(w(x) = \langle w, K(\cdot, x)\rangle = 0\) for every \(x\), so the closure of \(\mathcal{H}_0\) has trivial orthogonal complement and, by the projection theorem, is all of \(\tilde{\mathcal{H}}\). Now let \(f \in \mathcal{H}_K\) be the pointwise limit of an approximating sequence \(\{f_n\}\). This sequence is Cauchy in \(\tilde{\mathcal{H}}\) as well, so it converges there to some \(\tilde{f}\), and norm convergence in \(\tilde{\mathcal{H}}\) implies pointwise convergence by the bound \(|f_n(x) - \tilde{f}(x)| \leq \|f_n - \tilde{f}\|_{\tilde{\mathcal{H}}} \sqrt{K(x, x)}\). Hence \(\tilde{f} = f\), so \(f \in \tilde{\mathcal{H}}\) and \(\|f\|_{\tilde{\mathcal{H}}} = \lim_n \|f_n\| = \|f\|_{\mathcal{H}_K}\). Thus \(\mathcal{H}_K \subseteq \tilde{\mathcal{H}}\) with the same norm, hence, by polarization, with the same inner products. Conversely, given \(v \in \tilde{\mathcal{H}}\), density provides \(f_n \in \mathcal{H}_0\) with \(f_n \to v\) in \(\tilde{\mathcal{H}}\). Then \(\{f_n\}\) is an approximating sequence whose pointwise limit is \(v\), so \(v \in \mathcal{H}_K\). So \(\tilde{\mathcal{H}} = \mathcal{H}_K\) as Hilbert spaces of functions.

Proof sketch:

Continuity of \(K\) on the compact set \(\mathcal{X}\times\mathcal{X}\) and finiteness of \(\mu\) give \(K \in L^2(\mathcal{X}\times\mathcal{X}, \mu\otimes\mu)\), so \(T_K\) is a Hilbert-Schmidt operator and hence compact. Symmetry of \(K\) gives self-adjointness.

Positive definiteness of \(K\) is defined for finite point sets. It must be promoted to the integral statement \(\langle T_K f, f\rangle \geq 0\). Fix a continuous \(f \in C(\mathcal{X})\) and \(\eta \gt 0\). Intersecting \(\mathcal{X}\) with a grid of half-open cubes of side \(\eta / \sqrt{d}\) and discarding the empty intersections partitions it into finitely many nonempty Borel sets \(A_1, \ldots, A_m\) of diameter at most \(\eta\), and we pick sample points \(x_i \in A_i\). The discrete PD condition with \(c_i = f(x_i)\, \mu(A_i)\) gives \[ \sum_{i,j} K(x_i, x_j) f(x_i) f(x_j) \, \mu(A_i) \mu(A_j) \geq 0. \]

The function \(g(x, x') = K(x, x') f(x) f(x')\) is continuous on the compact set \(\mathcal{X} \times \mathcal{X}\), hence uniformly continuous by the Heine-Cantor theorem. Let \(\omega(\eta)\) be the supremum of \(|g(x, x') - g(y, y')|\) over points \((x, x'), (y, y') \in \mathcal{X} \times \mathcal{X}\) with \(|x - y|, |x' - y'| \leq \eta\), which tends to \(0\) as \(\eta \to 0\). Splitting the iterated integral \(\langle T_K f, f\rangle = \int \!\! \int g(x, x')\, d\mu(x')\, d\mu(x)\) over the sets \(A_i \times A_j\) shows that it differs from the left-hand side above by at most \(\mu(\mathcal{X})^2\, \omega(\eta)\). Letting \(\eta \to 0\) gives \(\langle T_K f, f\rangle \geq 0\) for all \(f \in C(\mathcal{X})\). The same argument is carried out in detail for \([a,b]\) with Lebesgue measure, and for complex Hermitian kernels, in Spectral Theory.

The density of \(C(\mathcal{X})\) in \(L^2(\mathcal{X}, \mu)\), a fact about finite Borel measures on compact metric spaces that we take for granted here, and continuity of \(f \mapsto \langle T_K f, f\rangle\) on \(L^2\) extend the inequality to all of \(L^2\). All eigenvalues of \(T_K\) are therefore nonnegative.

The Spectral Theorem for compact self-adjoint operators gives \(T_K f = \sum_n \lambda_n \langle f, e_n\rangle_{L^2} e_n\) with orthonormal eigenfunctions \(\{e_n\}\). Since the kernel \(K\) determines \(T_K\) uniquely as an integral operator (distinct kernels modulo a.e. equivalence define distinct integral operators), this lifts to the kernel decomposition \(K(x, x') = \sum_n \lambda_n e_n(x) e_n(x')\) with convergence in \(L^2(\mathcal{X}\times\mathcal{X}, \mu\otimes\mu)\).

The upgrade to absolute and uniform convergence on \(\mathcal{X}\times\mathcal{X}\) is the deep part. The right-hand side of \(T_K e_n = \lambda_n e_n\), namely \(x \mapsto \int K(x, x') e_n(x')\, d\mu(x')\), is continuous in \(x\) by continuity of \(K\) and dominated convergence.

Replacing \(e_n\) by \(\lambda_n^{-1} T_K e_n\) (valid for \(\lambda_n \gt 0\)) within its a.e. equivalence class therefore selects a continuous representative. Strict positivity of \(\mu\) ensures this representative is uniquely determined, because any two continuous functions agreeing a.e. with respect to a strictly positive measure must agree pointwise. The pointwise expansion is therefore well-defined.

The partial sums \(S_N(x, x') = \sum_{n=1}^N \lambda_n e_n(x) e_n(x')\) are continuous, and on the diagonal the nonnegative terms \(\lambda_n e_n(x)^2 \geq 0\) make \(S_N(x, x) \nearrow K(x, x)\) monotonically. Dini's theorem (continuous monotone sequence with continuous limit on a compact set converges uniformly) upgrades this to uniform convergence on the diagonal. For the off-diagonal terms, Cauchy-Schwarz applied to partial-sum tails gives, for \(M \gt N\), \[ |S_M(x, x') - S_N(x, x')|^2 = \left|\sum_{n=N+1}^M \lambda_n e_n(x) e_n(x')\right|^2 \leq R_N(x) \cdot R_N(x'), \] where \(R_N(x) = K(x, x) - S_N(x, x) \geq \sum_{n=N+1}^M \lambda_n e_n(x)^2\).

The diagonal uniform convergence \(R_N \to 0\) gives a uniform Cauchy criterion, yielding both absolute and uniform convergence on all of \(\mathcal{X}\times\mathcal{X}\).

Example: The RBF (Gaussian) Kernel

The radial basis function kernel \(K(x, x') = \exp\bigl(-\|x - x'\|^2 / (2\sigma^2)\bigr)\) is continuous, symmetric, and positive definite. For a Gaussian input measure on \(\mathbb{R}\), its eigenfunctions are Hermite-type functions and the eigenvalues decay exponentially: \(\lambda_n = C \cdot r^n\) with \(0 \lt r \lt 1\). (That measure is not supported on a compact set, so this example lies just outside the hypotheses of the theorem above.) This rapid decay explains why low-rank approximations of the Gram matrix, such as truncating the expansion after a few terms, work well in practice. Unless the bandwidth is small relative to the spread of the data, only the first few eigenfunctions carry significant weight. (Random Fourier Features rest on a different fact, Bochner's theorem, which represents a continuous positive-definite shift-invariant kernel normalized by \(K(x, x) = 1\) as the Fourier transform of a probability measure.)

Proof:

By Mercer's Theorem, \(K(x, y) = \sum_n \lambda_n e_n(x) e_n(y) = \sum_n \phi_n(x) \phi_n(y)\) with \(\phi_n := \sqrt{\lambda_n}\, e_n\) (continuous representatives). For a square-summable sequence \((c_n)\), the Cauchy-Schwarz inequality in \(\ell^2\) gives \[ \sum_{n \gt N} |c_n|\, |\phi_n(x)| \leq \Bigl(\sum_{n \gt N} c_n^2\Bigr)^{1/2} \sqrt{K(x, x)} \] (using \(\sum_n \phi_n(x)^2 = K(x, x)\), the Mercer expansion at \(x' = x\)), so \(\sum_n c_n \phi_n\) converges absolutely at every \(x\), and uniformly on \(\mathcal{X}\) because \(K\) is bounded on the compact \(\mathcal{X} \times \mathcal{X}\). Let \(\mathcal{H}'\) be the space of these functions with \(\langle \sum_n c_n \phi_n, \sum_n d_n \phi_n\rangle := \sum_n c_n d_n\). The coefficients are determined by the function: uniform convergence on the finite measure space implies convergence in \(L^2\), so \(\langle \sum_n c_n \phi_n, e_m\rangle_{L^2} = c_m \sqrt{\lambda_m}\) with \(\lambda_m \gt 0\). Hence \(\mathcal{H}'\) is a Hilbert space of functions, isometric to \(\ell^2\), with \(\{\phi_n\}\) as an orthonormal basis. Since \(\sum_n \phi_n(y)^2 = K(y, y)\), \(K(\cdot, y) = \sum_n \phi_n(y) \phi_n\) lies in \(\mathcal{H}'\), and \(\langle \sum_n c_n \phi_n, K(\cdot, y)\rangle = \sum_n c_n \phi_n(y)\), so \(K\) is the reproducing kernel of \(\mathcal{H}'\). By the uniqueness half of the Moore-Aronszajn Theorem, \(\mathcal{H}' = \mathcal{H}_K\) as Hilbert spaces of functions.

The spectral-calculus definition of \(T_K^{1/2}\) sends \(g = \sum_n g_n e_n \in L^2\) to \(T_K^{1/2} g = \sum_n \sqrt{\lambda_n}\, g_n\, e_n = \sum_n g_n \phi_n\) (the \(L^2\) sum and the uniformly convergent sum define the same class, and we take its continuous representative), whose \(\mathcal{H}_K\)-norm is \((\sum_n g_n^2)^{1/2} = \|g\|_{L^2}\). Thus \(T_K^{1/2} : L^2(\mathcal{X}, \mu) \to \mathcal{H}_K\) is norm-preserving, with image all of \(\mathcal{H}_K\) (every \(f = \sum_n c_n \phi_n \in \mathcal{H}_K\) is the image of \(g = \sum_n c_n e_n \in L^2\)).

Proof sketch:

By the Aronszajn Factorization Lemma, every \(f \in \mathcal{H}_K\) can be written uniquely as \(f = T_K^{1/2} h\) for some \(h \in L^2(\mathcal{X}, \mu)\), and this correspondence is an isometry: \(\|f\|_{\mathcal{H}_K} = \|h\|_{L^2}\). Expanding \(h\) in the \(L^2\)-orthonormal basis \(\{e_n\}\) as \(h = \sum_n h_n e_n\), we have \[ f = T_K^{1/2} h = \sum_n h_n\, T_K^{1/2} e_n = \sum_n h_n \sqrt{\lambda_n}\, e_n. \]

Comparing with the \(L^2\)-Fourier expansion \(f = \sum_n f_n e_n\) gives \(f_n = h_n \sqrt{\lambda_n}\), that is, \(h_n = f_n / \sqrt{\lambda_n}\). The isometry \(\|f\|_{\mathcal{H}_K}^2 = \|h\|_{L^2}^2\) then reads \[ \|f\|_{\mathcal{H}_K}^2 = \sum_n h_n^2 = \sum_n \frac{f_n^2}{\lambda_n}. \] The polarization identity yields the inner-product formula. The membership characterization \(f \in \mathcal{H}_K \iff \sum_n f_n^2/\lambda_n \lt \infty\) follows from \(f \in \mathcal{H}_K \iff h \in L^2 \iff \sum_n h_n^2 \lt \infty\).

Proof Sketch:

Decompose any \(f \in \mathcal{H}_K\) as \(f = f_\parallel + f_\perp\), where \(f_\parallel \in \operatorname{span}\{K(\cdot, x_i)\}_{i=1}^N\) and \(f_\perp\) is orthogonal to this subspace. (The span is finite-dimensional, hence closed in \(\mathcal{H}_K\), so this orthogonal decomposition is guaranteed by the projection theorem.)

By the reproducing property, \(f(x_i) = \langle f, K(\cdot, x_i) \rangle_{\mathcal{H}_K}\). Since \(f_\perp\) is orthogonal to every \(K(\cdot, x_i)\): \[ f(x_i) = f_\parallel(x_i) + \underbrace{\langle f_\perp, K(\cdot, x_i) \rangle}_{= 0} = f_\parallel(x_i). \]

The component \(f_\perp\) therefore does not affect the data-fit term. However, by Pythagoras: \[ \|f\|_{\mathcal{H}_K}^2 = \|f_\parallel\|_{\mathcal{H}_K}^2 + \|f_\perp\|_{\mathcal{H}_K}^2 \geq \|f_\parallel\|_{\mathcal{H}_K}^2. \] Adding any nonzero \(f_\perp\) strictly increases the regularization penalty without improving the data fit. Hence any minimizer satisfies \(f_\perp = 0\).