Why Orthogonal Projection Solves Interpolation
In a reproducing kernel Hilbert space, prescribing a function’s values at finitely many inputs imposes finitely many linear constraints. There may be many functions satisfying those constraints, and the constraints may even be incompatible. The Hilbert-space geometry gives a direct way to answer both questions: project a feasible function onto the span of the kernel sections associated with the observed inputs.
This projection preserves all the prescribed values while removing any component that contributes to the norm but not to those values. The result is the unique feasible function with smallest RKHS norm. A Gram matrix describes whether such a function exists and provides a finite-dimensional representation when it does.
Pointwise Constraints and the Relevant Subspace
Let \(\mathcal H\) be a real reproducing kernel Hilbert space on an input set \(\mathcal X\), with kernel \(k\). For each \(x\in\mathcal X\), write \(k_x=k(\,\cdot\,,x)\) for its kernel section. The reproducing property states that \(f(x)=\langle f,k_x\rangle_{\mathcal H}\) for every \(f\in\mathcal H\). Fix inputs \(x_1,\ldots,x_n\in\mathcal X\), which need not be distinct, and target values \(y=(y_1,\ldots,y_n)^\top\in\mathbb R^n\).
The subspace containing the relevant kernel sections is \(V=\operatorname{span}\{k_{x_1},\ldots,k_{x_n}\}\). It is finite-dimensional and therefore closed in \(\mathcal H\). The Gram matrix \(K\in\mathbb R^{n\times n}\) has entries \(K_{ij}=k(x_i,x_j)\). It is symmetric positive semidefinite, and repeated inputs or linear dependence among kernel sections can make it singular.
To see why \(V\) is the relevant subspace, consider any \(f\in\mathcal H\) and its orthogonal decomposition \(f=P_Vf+r\), where \(P_Vf\in V\) and \(r\perp V\). For every constraint point, \(r(x_i)=\langle r,k_{x_i}\rangle_{\mathcal H}=0\). Thus \(f\) and \(P_Vf\) have the same values at all constraint points.
Worked Example: Interpolation with the Linear Kernel
Take \(\mathcal X=\mathbb R^2\) and \(k(x,z)=x^\top z\). Its RKHS consists of the functions \(f_w(x)=w^\top x\), with \(\|f_w\|_{\mathcal H}=\|w\|_2\). Interpolate the values \(y_1=3\) at \(x_1=(1,0)^\top\) and \(y_2=4\) at \(x_2=(0,1)^\top\).
The kernel sections are \(k_{x_1}(x)=x_1^{\mathrm{coord}}\) and \(k_{x_2}(x)=x_2^{\mathrm{coord}}\), where \(x=(x_1^{\mathrm{coord}},x_2^{\mathrm{coord}})^\top\). They are orthonormal, so \(V=\mathcal H\) and \(K=\begin{pmatrix}1&0\\0&1\end{pmatrix}\). The interpolation equations are \(w_1=3\) and \(w_2=4\). Consequently the only feasible function is \(f(x)=3x_1^{\mathrm{coord}}+4x_2^{\mathrm{coord}}\), and its norm is \(\sqrt{3^2+4^2}=5\). In kernel-section form, it is \(3k_{x_1}+4k_{x_2}\).
Feasibility and the Minimum-Norm Theorem
The Gram matrix does more than encode inner products among the sections: its range exactly describes which target vectors can be interpolated. When interpolation is feasible, projection identifies the minimizer.
Proof. Define the linear evaluation map \(T:\mathcal H\to\mathbb R^n\) by \((Tf)_i=f(x_i)\). It is bounded because each evaluation is continuous in an RKHS: \(|f(x_i)|\leq\|f\|_{\mathcal H}\|k_{x_i}\|_{\mathcal H}\). Its adjoint is \(T^*a=\sum_{i=1}^n a_i k_{x_i}\), since \(\langle f,T^*a\rangle_{\mathcal H}=\sum_i a_i f(x_i)=\langle Tf,a\rangle_{\mathbb R^n}\). Therefore \(TT^*=K\): the \(i\)th entry of \(TT^*a\) is \(\sum_j a_j k(x_i,x_j)\).
For a linear map into the finite-dimensional space \(\mathbb R^n\), \(\operatorname{Range}(T)=(\ker T^*)^\perp\). Indeed, a vector \(a\) is orthogonal to \(\operatorname{Range}(T)\) exactly when \(\langle Tf,a\rangle=0\) for every \(f\), which is equivalent to \(T^*a=0\). Also, \(\ker(TT^*)=\ker(T^*)\), since \(\langle a,TT^*a\rangle=\|T^*a\|_{\mathcal H}^2\). As \(K=TT^*\) is symmetric, \(\operatorname{Range}(K)=(\ker K)^\perp=(\ker T^*)^\perp\). Hence \(\operatorname{Range}(T)=\operatorname{Range}(K)\). Feasibility means precisely \(y\in\operatorname{Range}(T)\), proving the feasibility characterization.
Now suppose \(y\) is feasible and choose \(f\in\mathcal H\) with \(Tf=y\). Write \(f=P_Vf+r\) with \(r\perp V\). The reproducing property gives \(r(x_i)=0\) at every constraint, so \(P_Vf\) is feasible too. Orthogonality gives \(\|f\|_{\mathcal H}^2=\|P_Vf\|_{\mathcal H}^2+\|r\|_{\mathcal H}^2\). Thus the projection has norm no greater than any feasible \(f\), and equality holds only if \(r=0\). This proves that the minimum-norm interpolant exists and belongs to \(V\). If \(p_1,p_2\in V\) are both feasible, then \(d=p_1-p_2\in V\) and \(d(x_i)=0\) for every \(i\). Hence \(\langle d,k_{x_i}\rangle_{\mathcal H}=0\) for every \(i\), so \(d\perp V\). Since \(d\in V\), \(d=0\), proving uniqueness.
Write \(p=\sum_j\alpha_jk_{x_j}\), which is possible because \(p\in V\). Its values are \(Tp=K\alpha\), so \(K\alpha=y\). Conversely, any \(\alpha\) satisfying this equation gives a feasible function in \(V\), which must be the unique minimum-norm interpolant. Finally, \(\|p\|_{\mathcal H}^2=\alpha^\top K\alpha=\alpha^\top y\). If \(\alpha'\) is another solution, then \(z=\alpha'-\alpha\in\ker K\); since \(y=K\alpha\), \(z^\top y=z^\top K\alpha=0\), so \((\alpha')^\top y=\alpha^\top y\). Further, \(\sum_i z_i k_{x_i}\) has squared norm \(z^\top Kz=0\), so it is the zero function. Thus the coefficients can differ while representing the same \(p\). \(\square\)
Worked Examples with Singular and Incompatible Constraints
Worked Example: A Singular Gram Matrix with Compatible Values
Again use the linear kernel on \(\mathbb R^2\), but now constrain \(f(1,0)=1\) and \(f(2,0)=2\). The Gram matrix and target vector are \[ K=\begin{pmatrix}1&2\\2&4\end{pmatrix}, \qquad y=\begin{pmatrix}1\\2\end{pmatrix}. \] The matrix has rank one and is singular. Nevertheless, \(K\alpha=y\) has solutions; for example, \(\alpha=(1,0)^\top\). This yields \(p=k_{(1,0)}\), or \(p(x)=x_1^{\mathrm{coord}}\), which has the required values.
Another solution is \(\alpha'=(0,\tfrac12)^\top\), because \(K\alpha'=(1,2)^\top\). It gives the same function: \(\tfrac12 k_{(2,0)}(x)=\tfrac12(2x_1^{\mathrm{coord}})=x_1^{\mathrm{coord}}\). The minimum squared norm is \(\alpha^\top y=1\), so the minimum norm is \(1\). This example shows why singularity alone does not imply infeasibility, and why coefficient uniqueness is not required for function uniqueness.
Worked Example: Detecting Incompatible Values
With the same kernel, take \(x_1=(1,0)^\top\) and \(x_2=(2,0)^\top\), but prescribe \(y=(1,3)^\top\). The Gram matrix is still \(\begin{pmatrix}1&2\\2&4\end{pmatrix}\). Its columns are multiples of \((1,2)^\top\), so its range is \(\operatorname{span}\{(1,2)^\top\}\). The target \((1,3)^\top\) is not in that range: if it were \(c(1,2)^\top\), the first coordinate would force \(c=1\), while the second would then be \(2\), not \(3\).
Therefore the constraints are infeasible. The same conclusion follows directly from the model: every \(f_w(x)=w^\top x\) satisfies \(f_w(2,0)=2f_w(1,0)\), whereas the requested values would require \(3=2(1)\). No choice of coefficient vector can solve the inconsistent constraints.
Worked Example: A Linear Dependency Among Three Sections
Use the linear kernel on \(\mathbb R^2\) at \(x_1=(1,0)^\top\), \(x_2=(0,1)^\top\), and \(x_3=(1,1)^\top\). Their Gram matrix is \[ K=\begin{pmatrix}1&0&1\\0&1&1\\1&1&2\end{pmatrix}. \] The third input is the sum of the first two, so every linear function must satisfy \(f(x_3)=f(x_1)+f(x_2)\). The target \(y=(1,2,3)^\top\) obeys this identity and is feasible. Specifically, \(\alpha=(1,2,0)^\top\) satisfies \(K\alpha=(1,2,3)^\top\), giving \(p(x)=x_1^{\mathrm{coord}}+2x_2^{\mathrm{coord}}\). Its squared norm is \(\alpha^\top y=1+4=5\).
Changing only the third target to \(4\) violates the necessary identity. Equivalently, every vector in the range of \(K\) has third coordinate equal to the sum of its first two, while \((1,2,4)^\top\) does not. These constraints are therefore infeasible.
Why the Projection View Matters
The projection argument explains a useful structural fact: when finite pointwise constraints are feasible, the minimum-norm solution can be expressed using only the kernel sections at the constraint inputs. Components orthogonal to their span vanish at every constrained point, so they cannot help meet the constraints. The minimizer excludes those components because they would add squared norm.
The Gram-matrix condition is also a practical diagnostic. For a singular matrix, do not assume either that the constraints are infeasible or that the interpolating function is nonunique. Check whether \(y\) lies in \(\operatorname{Range}(K)\). If it does, the minimum-norm function is unique, even though multiple coefficient vectors may describe it. If it does not, no function in the RKHS can meet all the stated values.
Common Pitfall
A subtle error is to claim that adding any nonzero function orthogonal to \(V\) to any feasible function must increase its norm. That claim is false: an arbitrary feasible function may already have a nonzero orthogonal component, and adding another orthogonal function could cancel it. For example, with the linear kernel on \(\mathbb R^2\) and constraint \(f(1,0)=1\), \(f(x)=x_1^{\mathrm{coord}}+x_2^{\mathrm{coord}}\) is feasible, and \(h(x)=-x_2^{\mathrm{coord}}\) is nonzero and orthogonal to \(V=\operatorname{span}\{k_{(1,0)}\}\). Adding \(h\) produces \(p(x)=x_1^{\mathrm{coord}}\), the minimum-norm interpolant.
The correct claim is about adding a nonzero orthogonal function to the minimum-norm interpolant itself, or to its projection onto \(V\). If \(p\in V\) is the minimum-norm interpolant and \(0\ne h\perp V\), then \(p+h\) remains feasible, but \(\|p+h\|_{\mathcal H}^2=\|p\|_{\mathcal H}^2+\|h\|_{\mathcal H}^2>\|p\|_{\mathcal H}^2\). The orthogonality ensures both that the constrained values are unchanged and that the norm strictly increases.
Check Your Understanding
Use the projection and Gram-matrix criteria to answer the following.
- Why does a component orthogonal to every constraint-point kernel section vanish at every constrained input?
- State the necessary and sufficient condition on \(y\) and \(K\) for the interpolation problem to be feasible.
- What remains unique when \(K\) is singular and the constraints are feasible: the coefficient vector, the interpolating function, or both?
- For a feasible coefficient vector \(\alpha\), give a formula for the squared norm of the minimum-norm interpolant.
- Why can adding a nonzero function orthogonal to \(V\) reduce the norm of an arbitrary feasible function but not of the minimum-norm interpolant?