The Representer Theorem by Orthogonal Decomposition

Why the Minimizer Has a Finite-Dimensional Form

An RKHS can be infinite-dimensional, so optimizing over all its functions may appear to require infinitely many degrees of freedom. But an empirical objective built from finitely many observed input points only evaluates a candidate function at those points. The reproducing property links each such evaluation to one kernel section, making it possible to separate the part of a function that affects the data from the part that does not.

The key is the penalty: if it strictly increases with the RKHS norm, adding a nonzero component that has no effect on the observed evaluations can only make the objective worse. The argument is geometric and does not require a convex loss.

Because \(\mathcal S\) is finite-dimensional, it is a closed subspace of \(\mathcal H\). Every \(f\in\mathcal H\) therefore has a unique orthogonal decomposition \(f=g+h\), where \(g\in\mathcal S\) and \(h\in\mathcal S^\perp\). The component \(g\) is the orthogonal projection of \(f\) onto \(\mathcal S\); \(h\) is the residual.

Projection Preserves the Observed Evaluations

The reproducing property states that \(f(x)=\langle f,k_x\rangle_{\mathcal H}\) for every \(f\in\mathcal H\) and \(x\in\mathcal X\). Since each observed section \(k_{x_i}\) belongs to \(\mathcal S\), any \(h\in\mathcal S^\perp\) is orthogonal to it. Thus \(h(x_i)=0\): the residual vanishes at every observed input.

Proof. Since \(k_{x_i}\in\mathcal S\) and \(h\perp\mathcal S\), the reproducing property gives \(h(x_i)=\langle h,k_{x_i}\rangle_{\mathcal H}=0\). Therefore \(f(x_i)=g(x_i)+h(x_i)=g(x_i)\). Orthogonality of \(g\) and \(h\) gives the Pythagorean identity for the squared norm. If \(h\ne0\), then \(\|h\|_{\mathcal H}^2>0\), so \(\|f\|_{\mathcal H}^2>\|g\|_{\mathcal H}^2\), and hence \(\|f\|_{\mathcal H}>\|g\|_{\mathcal H}\). \(\square\)

This proposition identifies both sides of the argument: projection leaves the data fit unchanged and, unless the residual is zero, strictly reduces the norm. It does not yet say which functions minimize an objective. For that conclusion, the penalty must respond strictly to the norm reduction.

The Representer Theorem by Orthogonal Decomposition

Consider an objective whose empirical loss depends on \(f\) only through its values at the observed inputs. Allow the loss to be any real-valued function \(\Phi\) of those values, and let the norm penalty be \(\Omega(\|f\|_{\mathcal H})\).

Proof. Take any \(f\in\mathcal H\), and decompose it as \(f=g+h\) with \(g\in\mathcal S\) and \(h\in\mathcal S^\perp\). By the proposition, \(f(x_i)=g(x_i)\) at every observed input. Thus the empirical loss is identical at \(f\) and \(g\). If \(h\ne0\), then \(\|g\|_{\mathcal H}<\|f\|_{\mathcal H}\). Strict increase of \(\Omega\), together with \(\lambda>0\), then gives $$ J(g)=\Phi\bigl(f(x_1),\ldots,f(x_n)\bigr)+\lambda\Omega(\|g\|_{\mathcal H}) < \Phi\bigl(f(x_1),\ldots,f(x_n)\bigr)+\lambda\Omega(\|f\|_{\mathcal H}) =J(f). $$ If \(f\) were a minimizer with \(h\ne0\), this strict inequality would contradict its minimality. Every minimizer must therefore have \(h=0\), so it belongs to \(\mathcal S\). By the definition of \(\mathcal S\), it has the stated expansion. \(\square\)

The existence condition matters: the theorem says that any minimizer, if attained, lies in the indicated span. It does not assert that an arbitrary empirical loss and penalty guarantee attainment. Nor does the conclusion say that the coefficients \(\alpha_i\) are unique; the observed kernel sections might be linearly dependent.

Proof. Since \(\mathcal S\subseteq\mathcal H\), the infimum over \(\mathcal H\) is at most the infimum over \(\mathcal S\). Conversely, for every \(f\in\mathcal H\), its projection \(g\in\mathcal S\) satisfies \(J(g)\le J(f)\): the losses agree, and the projection cannot increase the norm, so it cannot increase the penalty. Therefore the infimum over \(\mathcal S\) is at most \(J(f)\) for every \(f\in\mathcal H\), and hence at most the infimum over \(\mathcal H\). The two infima are equal. \(\square\)

Worked Examples

What the Result Does—and Does Not—Require

The theorem reduces the search for minimizers to a finite-dimensional subspace generated by the observed kernel sections. The crucial properties are that the empirical loss sees only the observed evaluations and that a nonzero orthogonal residual increases the penalty. The RKHS can remain infinite-dimensional; it is the objective's dependence on finitely many evaluations that makes this particular reduction possible.

A common mistake is to reason that projection “does not change the loss,” then conclude that every minimizer can be projected without changing the objective. The loss is unchanged, but the penalty generally decreases strictly. With a strictly increasing penalty, that means a function with a nonzero orthogonal component is not a minimizer at all. This strictness is what establishes that every minimizer is in the span.

If the penalty is not strictly increasing, that conclusion can fail. For example, in \(\mathbb R^2\), consider the objective \(J(a,b)=(a-1)^2\), which uses one evaluation along the first coordinate and a constant penalty. Every \((1,b)\) is a minimizer, including points outside the first-coordinate span. Projection still produces a minimizer in the span, but it does not force all minimizers to lie there. Also, the theorem’s conclusion applies to evaluation-based losses as stated; if an objective depends on other function information, such as derivatives, the relevant finite-dimensional subspace need not be the span of the observed kernel sections alone.