A Reproducing Kernel Hilbert Space (RKHS) is a Hilbert space of functions where point evaluation is a continuous linear functional — meaning you can evaluate any function at any point without pathological behavior. Every RKHS is uniquely associated with a positive definite kernel k via the reproducing property: f(x) = <f, k(x, ·)>. This theoretical foundation explains why kernel methods work: the kernel defines both the function space and its geometry. Mercer's theorem connects positive definite kernels to feature maps, and the RKHS norm provides a natural regularizer that controls function complexity.
You have already used kernels practically — computing k(x, y) to implicitly work in high-dimensional feature spaces. The theory of RKHS explains why this works and what the kernel is really doing. A Reproducing Kernel Hilbert Space is not just any function space; it is a Hilbert space where the kernel acts as a bridge between the space of functions and the evaluation of those functions at points.
The reproducing property — f(x) = <f, k(x, ·)> — says that to evaluate function f at point x, you take the inner product of f with the kernel function anchored at x. This is powerful because it means point evaluation is a continuous operation: small perturbations to f in the RKHS norm produce small changes in f(x). In L^2, the standard space of square-integrable functions, this fails catastrophically — you can change a function on a single point without changing its L^2 norm at all, so "the value at point x" is not a meaningful continuous operation. The RKHS fixes this by building point evaluation into the fabric of the space, making it the natural setting for supervised learning where predictions must be evaluated at specific inputs.
Mercer's theorem provides the spectral decomposition that connects RKHS theory to the feature-map intuition. A continuous positive definite kernel on a compact domain decomposes as k(x, y) = sum_i lambda_i * phi_i(x) * phi_i(y), where lambda_i and phi_i are the eigenvalues and eigenfunctions of the integral operator associated with the kernel. The feature map is phi(x) = (sqrt(lambda_1) * phi_1(x), sqrt(lambda_2) * phi_2(x), ...), and k(x, y) = <phi(x), phi(y)>. For the RBF kernel, this decomposition is infinite-dimensional but the eigenvalues decay exponentially, meaning the effective dimensionality is finite and functions in the RKHS are infinitely smooth. For polynomial kernels, the decomposition is finite-dimensional and the eigenfunctions correspond to polynomial features.
The RKHS norm ||f|| provides a natural, principled measure of function complexity. Penalizing this norm during learning — as kernel ridge regression and SVMs implicitly do — restricts the learned function to be "simple" in the geometry defined by the kernel. This is not an ad hoc choice: the representer theorem (covered next) proves that the optimal solution to any RKHS-regularized problem lies in the span of kernel functions at the training points, making the optimization finite-dimensional despite the RKHS being infinite-dimensional. The entire theoretical edifice — kernel, RKHS, norm, representer theorem — forms a coherent framework that justifies kernel-based learning from first principles.