Motivation
A Gram matrix lets us calculate with a kernel on finitely many observations. A learning rule, however, returns a function that can be evaluated away from those observations. To understand what its norm means, we need a space containing the kernel sections and their limits. Simply declaring that a suitable Hilbert space exists leaves an important gap: why should a positive semidefinite function determine a well-defined inner product, and why should completion still produce actual functions rather than abstract objects with no pointwise interpretation?
The construction answers both questions. We start with finite formal combinations of kernel sections, remove vectors of zero length, and then complete the resulting inner-product space. Evaluation is continuous before completion, so it extends to the limit. The reproducing identity both identifies those limits as functions and prevents distinct abstract vectors from representing the same function. This is a concrete example of how functional analysis supports a computational method.
The later optimization argument uses two different forms of geometry. Orthogonal projection onto the observed kernel span explains why a norm penalty eliminates all invisible components. The eigenvalues of the finite Gram matrix then explain how regularization modifies fitted observations. These facts distinguish the norm of a function from the Euclidean norm of an arbitrary coefficient representation, a distinction that becomes unavoidable for singular kernels.
Definitions
Definition 5.1.1
(Kernel sections and the formal bilinear form)
Let be any set and let be symmetric and positive semidefinite: every finite Gram matrix has nonnegative quadratic form. Introduce formal symbols , and let consist of their finite linear combinations. Define
Formal combinations are collected by equal indices in the usual vector-space way. Positivity gives , but it need not be strictly positive for nonzero formal vectors.
Write . A quotient vector means that adding a vector in makes no difference. A completion will be defined through Cauchy sequences of these quotient vectors, with sequences considered equal when their difference tends to zero in norm. These definitions are needed because finite kernel spans are not always complete.
A Hilbert space of functions has reproducing kernel if and for every and . In particular evaluation at each fixed point is a continuous linear functional. No uniform bound over is included in this definition: the norm of evaluation can depend on the point.
Theorem/Proposition
Theorem 5.1.2
(Construction and uniqueness of the reproducing space)
Every real symmetric positive semidefinite kernel determines a Hilbert space of functions on such that
The finite linear span of its kernel sections is dense. Any other function Hilbert space with the same reproducing kernel is identical up to the isometry that preserves every represented function.
Theorem 5.1.3
(Observed spans, interpolation, and normalized ridge)
For data , put and . If an empirical objective depends only on and adds a strictly increasing function of , every existing minimizer lies in . For , the normalized squared objective
has a unique function minimizer with canonical coefficients . Exact interpolation is possible precisely when . In that case the unique interpolating function of minimum norm has coefficients and squared norm .
Existence of a minimizer is asserted here for the squared ridge objective, not for every possible empirical loss and penalty. A strictly increasing penalty gives the span conclusion conditional on existence. A strictly positive definite kernel, meaning positive Gram forms at distinct points for every nonzero coefficient vector, makes invertible at distinct observations. Positive semidefiniteness alone does not.
Proof sketch or proof idea
Proof
(Quotient, functions and completion)
Positivity implies a Cauchy–Schwarz inequality even before taking a quotient. The quadratic polynomial is nonnegative for every real . If , minimizing that polynomial gives . If , its linear term must vanish, so for every . In particular a zero-length vector pairs to zero with everything. This proves that is a subspace and that is unchanged by replacing either argument with another representative of the same quotient class. The induced form on is now a genuine inner product.
Map a quotient vector to the function . It is well-defined because null vectors pair to zero, and Cauchy–Schwarz gives the evaluation bound. It is injective: if is zero everywhere and , then , so . The symbol becomes exactly the section , because . We have constructed an inner-product space of actual functions.
Now take its completion. For Cauchy sequences and , their norms are bounded, and Cauchy–Schwarz shows that is Cauchy. Define their completed inner product as its limit. Replacing a sequence by an equivalent one leaves that limit unchanged. The norm is positive definite on equivalence classes: zero limiting norm means equivalence with the zero sequence. The resulting space is complete. One direct verification chooses, from each member of a Cauchy sequence of completed vectors, a finite-span approximant within ; those approximants form a Cauchy sequence and represent the required limit.
For each fixed , the evaluation bound makes Cauchy, so define as its limit. Equivalent sequences give the same value. Passing to the limit in the finite-span identity gives . There remains a crucial injectivity check: if all these values vanish, is orthogonal to every kernel section and hence to their dense finite span. Approximating by that span forces . Thus the completed vectors really are uniquely identified functions. The norm of follows by evaluating its inner product with itself.
Proof X-ray
What completion adds, and what it preserves
Positive semidefiniteness is used exactly once, to make a nonnegative quadratic; everything in the quotient step follows from the Cauchy–Schwarz inequality it yields, including the fact that null vectors pair to zero with everything. Symmetry makes a symmetric form, so the quotient carries a genuine inner product. The key move is the evaluation bound : it makes evaluation at each fixed point continuous, so values pass to Cauchy limits in the kernel norm. Completion therefore adds limits of Cauchy sequences in that norm, not arbitrary pointwise limits; norm convergence implies pointwise convergence, but the converse generally fails. The argument closes with the dense-span step, which prevents completion from creating a nonzero vector whose function values all vanish. A pointwise definition alone would not establish a faithful Hilbert-space representation.
Proof
(Uniqueness of the reproducing space)
For uniqueness, identify finite kernel combinations in any two candidate spaces. Their inner products are the same finite Gram sums, so this identification is an isometry. The sections have dense span in either space: a function orthogonal to all sections vanishes everywhere and is therefore zero. Extending the isometry by Cauchy limits gives an onto isometry, and bounded evaluation shows it preserves each function value.
The second theorem concerns the finite observed span and needs only projection and finite-dimensional linear algebra.
Proof
(Projection, ridge and interpolation)
For learning, is finite dimensional and therefore closed. Orthogonally decompose with . Then , whereas . Removing a nonzero leaves observations unchanged and strictly reduces the norm penalty. For ridge, the restriction to is continuous and coercive, so a bounded minimizing sequence has a convergent subsequence. Strict convexity of the squared norm gives uniqueness of the function. Hilbert-space differentiation gives
Taking yields . This matrix is positive definite even if is singular. Direct differentiation with respect to arbitrary coefficients instead produces ; canceling without invertibility is unjustified.
Interpolation reduces to , because the orthogonal remainder never changes training values. In an orthonormal eigenbasis , solve the positive-eigenvalue coordinates by division and require the zero-eigenvalue label coordinates to vanish. This is precisely . The coefficient gives a function in ; adding a coefficient in changes no function, since its squared kernel norm is zero. Adding a nonzero orthogonal function increases the norm. Therefore the minimum-norm interpolant is unique, and its squared norm is .
Spectral regularization is a function-space statement
Ridge fitted values have eigen-coordinates . Directions with small positive eigenvalues are shrunk more strongly, while a zero-eigenvalue label component cannot be fitted at all. As decreases, fitted values tend to the projection of onto . When interpolation is possible, the functions tend to the minimum-norm interpolant. Canonical coefficients themselves can diverge in null directions when labels have an incompatible null component; those divergent coefficients represent the zero function. This is why coefficient length is a poor substitute for the Hilbert norm.
Worked examples
Worked example 5.1.4
(A completion with genuinely new functions)
On , take when and zero otherwise. Finite kernel combinations are finitely supported sequences with their usual Euclidean norm. Completion gives , not just the finite sequences. The function belongs because , and its finite truncations converge in norm. Evaluation at index is inner product with the th coordinate vector. By contrast, the constant-one function is a pointwise limit of finite truncations but is not in ; the truncations are not Cauchy in the kernel norm.
Worked example 5.1.5
(A constant kernel separates coefficients from functions)
Let and observe two points with labels . The space contains only constant functions, and is the all-ones matrix. Interpolation is impossible because the labels are not in its one-dimensional range. With , the canonical system has matrix with rows and , giving . The learned constant is , agreeing with direct minimization of . Coefficients differing by represent the same function. Only their sum determines its squared Hilbert norm, namely .
Concept lensStructural
The space read off from a feature map
Suppose for a feature map , and let be the span of all . Then , and is an isometry from onto sending to , because both sides have inner products . A vector orthogonal to changes no function value, so is the least Euclidean length of a representing .
Worked example 5.1.6
(Finite polynomial features)
For , use features . Because these coordinate functions are linearly independent on the real line, the reproducing space is the quadratic polynomials , with squared norm . Evaluation at has norm , as the diagonal kernel is . Cauchy–Schwarz gives , and equality is attained when the coefficient vector is proportional to . The evaluation bound is therefore exact, not merely formal.
Common mistakes
Counterexample mode
Positive entries are not a positive semidefinite kernel
On a two-point set, assign diagonal entries one and off-diagonal entries two. Every similarity value is positive, but the coefficient vector has Gram quadratic form . The quotient construction fails because the starting form is not nonnegative. Symmetry and nonnegative diagonal entries are necessary but insufficient conditions.
Common mistake
(Treating completion as closure under pointwise limits)
Completion adds only limits of sequences that are Cauchy in the kernel norm. In the delta-kernel example, the truncations of the constant-one function converge pointwise, but they are not Cauchy and the constant-one function is not in . A reproducing space likewise need not contain every continuous function on its domain.
Common mistake
(Reading a singular Gram matrix as a nonunique function)
A singular does not make the regularized function nonunique. It can mean only that redundant coefficients represent the same function: in the constant-kernel example, and give the same constant .
The factor comes from the explicitly averaged loss; replacing it by changes the stated optimization problem. None of these algebraic facts alone supplies a population generalization rate.
Summary
Positive semidefiniteness gives a seminorm; quotienting removes its null vectors; completion supplies the missing Cauchy limits; bounded evaluation and dense sections identify those limits as functions. Projection onto the observed span then makes interpolation and ridge learning finite dimensional without confusing function norms with coefficient norms.
Exercises
Quick check
(Prove that forces for every .)
Apply Cauchy–Schwarz to the sections and .
Solution · Answer
Cauchy–Schwarz for the kernel sections gives . Thus the entire row and column vanish. This also follows by requiring the corresponding two-point quadratic polynomial to be nonnegative for every coefficient.
Quick check
(For the constant kernel and equal labels , find the minimum-norm interpolant and its squared norm.)
Find the range of the all-ones matrix and its pseudoinverse.
Solution · Answer
The only interpolating constant is , whose squared norm is four. Here , so canonical minimum-norm coefficients are and . Other coefficients with sum two represent exactly the same function.
Quick check
(For a Gram eigenvalue , and , calculate the fitted-value shrinkage factor. What happens at ?)
The shrinkage factor is .
Solution · Answer
The factor is . At zero eigenvalue the fitted component is zero, regardless of the label component. Regularization ensures a solvable coefficient system but cannot create a missing function direction.
Quick check
(For the kernel on , compare convergence of for and zero otherwise with convergence of the truncations of .)
Compute the kernel-norm distance between two members of each sequence.
Solution · Answer
Both sequences converge pointwise to their stated targets. The first has squared norm , and any distinct truncations have squared distance , so it is not Cauchy. The second has squared tail distance bounded by , so it converges in the reproducing-space norm to . Pointwise convergence alone does not decide membership of the limit.