Geometry Of Minimum-Norm Interpolation

Why Geometry Matters for Interpolation

In an underdetermined linear regression problem, there are more coefficients than observations. Consequently, the equations specifying an exact fit may admit many coefficient vectors. Interpolation identifies the set of vectors that fit the observed responses, but it does not by itself choose one of them. The Euclidean norm provides a geometric selection rule: among all exact fits, choose the coefficient vector closest to the origin.

This tutorial characterizes that set and derives the selection rule from orthogonal projection. The result is a fact about finite-dimensional linear algebra; it does not assert that the minimum-norm interpolator has the best prediction risk or that small coefficient norm guarantees good generalization.

The Interpolation Equations and Their Solution Set

Let $\mathbf X\in\mathbb R^{n\times p}$ be a design matrix, let $y\in\mathbb R^n$ be the response vector, and let $\beta\in\mathbb R^p$ be a coefficient vector. Exact interpolation means solving

\mathbf X\beta=y.

The system is consistent if at least one $\beta$ satisfies these equations. Equivalently, $y$ belongs to the column space of $\mathbf X$. The system is underdetermined when $p>n$, but this inequality alone does not guarantee consistency: for example, a rank-deficient matrix may fail to produce some response vectors.

Definition: The nullspace of $\mathbf X$ is $\ker(\mathbf X)=\{v\in\mathbb R^p:\mathbf Xv=0\}$. The row space of $\mathbf X$, denoted $\operatorname{row}(\mathbf X)$, is the subspace of $\mathbb R^p$ spanned by its rows. A minimum-norm interpolator is a solution of $\mathbf X\beta=y$ minimizing the Euclidean norm $\|\beta\|_2$ over all solutions.

Suppose the equations are consistent and choose one solution $\beta_0$. If $v\in\ker(\mathbf X)$, then $\mathbf X(\beta_0+v)=y$, so $\beta_0+v$ is also a solution. Conversely, if $\beta$ and $\beta_0$ are both solutions, then $\mathbf X(\beta-\beta_0)=0$, so their difference lies in the nullspace. Thus the solution set is an affine translate of the nullspace.

Theorem: If $\mathbf X\beta=y$ is consistent and $\beta_0$ is any one solution, then its complete solution set is $$ \{\beta:\mathbf X\beta=y\}=\beta_0+\ker(\mathbf X) =\{\beta_0+v:v\in\ker(\mathbf X)\}. $$

Worked Example: A One-Equation Interpolation Set

Let $\mathbf X=\begin{bmatrix}1&1\end{bmatrix}$ and $y=2$. The interpolation equation is $\beta_1+\beta_2=2$. Taking $\beta_0=(2,0)^\top$, and solving $v_1+v_2=0$, gives $\ker(\mathbf X)=\{t(1,-1)^\top:t\in\mathbb R\}$. Therefore every interpolator is

\beta(t)= \begin{bmatrix}2\\0\end{bmatrix} +t\begin{bmatrix}1\\-1\end{bmatrix} = \begin{bmatrix}2+t\\-t\end{bmatrix},\qquad t\in\mathbb R.

Substitution verifies the fit: $(2+t)+(-t)=2$ for every $t$. The infinitely many solutions form a line in coefficient space.

Orthogonal Projection Selects the Minimum-Norm Fit

The row space and nullspace of a real matrix are orthogonal complements in coefficient space: $\operatorname{row}(\mathbf X)=\ker(\mathbf X)^\perp$. Indeed, if $u$ is in the row space, it has the form $\mathbf X^\top a$, and if $v\in\ker(\mathbf X)$, then $u^\top v=a^\top\mathbf Xv=0$. Their dimensions sum to $p$ by the rank-nullity theorem, so this orthogonality identifies the full complement.

Let $P_{\operatorname{row}(\mathbf X)}$ denote orthogonal projection onto the row space. Starting from any interpolator $\beta_0$, project it onto that space. The discarded component lies in the nullspace, so removing it does not change the fitted values. Orthogonality also shows that the projected vector has strictly smaller norm unless the discarded component is zero.

Theorem: If $\mathbf X\beta=y$ is consistent, its unique minimum-norm solution is $$ \beta_{\min}=P_{\operatorname{row}(\mathbf X)}\beta_0 $$ for any interpolator $\beta_0$. Equivalently, it is the unique solution in $\operatorname{row}(\mathbf X)$.

Proof. Decompose $\beta_0$ into its orthogonal row-space and nullspace components: $\beta_0=P_{\operatorname{row}(\mathbf X)}\beta_0+v$, where $v\in\ker(\mathbf X)$. Since $\mathbf Xv=0$, the projected vector has the same fitted values:

\mathbf X P_{\operatorname{row}(\mathbf X)}\beta_0 =\mathbf X(\beta_0-v) =\mathbf X\beta_0 =y.

For any other interpolator $\beta$, the difference $\beta-\beta_{\min}$ belongs to $\ker(\mathbf X)$. Since $\beta_{\min}$ lies in the row space, the two vectors are orthogonal. Hence

\|\beta\|_2^2 =\|\beta_{\min}\|_2^2+\|\beta-\beta_{\min}\|_2^2 \geq \|\beta_{\min}\|_2^2.

Equality holds only if $\beta=\beta_{\min}$. This proves both minimality and uniqueness. $\square$

The Pseudoinverse Formula

The same geometry gives a formula that does not require first finding an arbitrary solution. Let $r=\operatorname{rank}(\mathbf X)$. A compact singular value decomposition is $\mathbf X=U_rD_rV_r^\top$, where the columns of $U_r\in\mathbb R^{n\times r}$ and $V_r\in\mathbb R^{p\times r}$ are orthonormal, and $D_r$ is diagonal with positive diagonal entries. Define the Moore–Penrose pseudoinverse by $\mathbf X^\dagger=V_rD_r^{-1}U_r^\top$.

Theorem: If $\mathbf X\beta=y$ is consistent, then $$ \beta_{\min}=\mathbf X^\dagger y. $$ If $\mathbf X$ has full row rank, so $r=n$, this reduces to $$ \beta_{\min}=\mathbf X^\top(\mathbf X\mathbf X^\top)^{-1}y. $$

Proof. Consistency means $y$ lies in the column space of $\mathbf X$, which is spanned by the columns of $U_r$. Thus $y=U_rc$ for some $c\in\mathbb R^r$. The pseudoinverse formula gives $\mathbf X^\dagger y=V_rD_r^{-1}c$, a vector in the row space of $\mathbf X$. Further,

\mathbf X\mathbf X^\dagger y =U_rD_rV_r^\top V_rD_r^{-1}U_r^\top y =U_rU_r^\top y =y,

because $U_rU_r^\top$ projects onto the column space and $y$ belongs to it. The vector $\mathbf X^\dagger y$ is therefore an interpolator in the row space, so the preceding theorem identifies it as the unique minimum-norm solution.

If $\mathbf X$ has full row rank, then $\mathbf X\mathbf X^\top$ is invertible and the pseudoinverse is $\mathbf X^\dagger=\mathbf X^\top(\mathbf X\mathbf X^\top)^{-1}$. To verify the inverse exists, for any nonzero $a\in\mathbb R^n$, $a^\top\mathbf X\mathbf X^\top a=\|\mathbf X^\top a\|_2^2>0$; full row rank makes $\mathbf X^\top a\neq0$. Substitution yields the stated expression. $\square$

Worked Example: Full Row Rank With Three Coefficients

Take $\mathbf X=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}$ and $y=(1,2)^\top$. Writing $\beta=(a,b,c)^\top$, the equations give $a=1-c$ and $b=2-c$. Every interpolator is therefore $\beta(c)=(1-c,2-c,c)^\top$.

Minimize the squared norm: $\|\beta(c)\|_2^2=(1-c)^2+(2-c)^2+c^2=5-6c+3c^2$. Its derivative is $-6+6c$, which is zero at $c=1$; since the quadratic coefficient is $3>0$, this is the unique minimum. The solution is $(0,1,1)^\top$, and direct substitution gives $\mathbf X\beta=(1,2)^\top$.

The full-row-rank formula confirms the result. Here $\mathbf X\mathbf X^\top=\begin{bmatrix}2&1\\1&2\end{bmatrix}$, with inverse $\frac13\begin{bmatrix}2&-1\\-1&2\end{bmatrix}$. Therefore $(\mathbf X\mathbf X^\top)^{-1}y=(0,1)^\top$, and $\mathbf X^\top(0,1)^\top=(0,1,1)^\top$.

Worked Example: A Rank-Deficient Design

Let $\mathbf X=\begin{bmatrix}1&2&0\\2&4&0\end{bmatrix}$ and $y=(3,6)^\top$. The second equation is twice the first, so the system is consistent and its only constraint is $\beta_1+2\beta_2=3$. The coefficient $\beta_3$ is unrestricted. Thus $\ker(\mathbf X)=\{(-2t,t,s)^\top:t,s\in\mathbb R\}$.

The rows span the direction $(1,2,0)^\top$. The minimum-norm interpolator must lie in this row space, so write it as $q(1,2,0)^\top$. The constraint gives $q+2(2q)=5q=3$, hence $q=3/5$ and $\beta_{\min}=(3/5,6/5,0)^\top$. It fits because $3/5+2(6/5)=3$, and the second row consequently gives $6$. Any other fit differs by a nullspace vector orthogonal to this row-space vector, so its squared norm is larger by the squared norm of that difference.

What the Geometry Does—and Does Not—Say

The minimum-norm rule resolves the algebraic nonuniqueness of interpolation. It selects a unique coefficient vector even when there are infinitely many exact fits, and the nullspace description explains exactly which coefficient changes leave the observed fitted values unchanged. In the full-row-rank case, the nullspace has dimension $p-n$; in general, its dimension is $p-\operatorname{rank}(\mathbf X)$.

A common mistake is to say that an underdetermined system always has a solution because it has more coefficients than equations. The correct condition is consistency: $y$ must belong to the column space of $\mathbf X$. Another mistake is to assume that exact fit uniquely determines the coefficients. It does so only when the nullspace is trivial; in an underdetermined system with $p>n$, the nullspace is nontrivial. The minimum-norm criterion is an additional selection rule, not a consequence of fitting the data alone.

Finally, “minimum norm” here always refers to the ordinary Euclidean norm of the coefficient vector. It is a precise geometric property of this chosen coordinate system and criterion. It does not, without further assumptions, imply that the selected interpolator is statistically preferable or predicts well on new observations.

Check Your Understanding

Use the geometry of the solution set to answer these questions.

Why is the difference between any two interpolators in $\ker(\mathbf X)$?
For a consistent system, why does projecting an interpolator onto $\operatorname{row}(\mathbf X)$ preserve its fitted values?
What condition on $y$ guarantees that $\mathbf X\beta=y$ has a solution?
In the full-row-rank case, why is $\mathbf X\mathbf X^\top$ invertible?
Does choosing the minimum-Euclidean-norm interpolator alone imply good prediction on new data? Explain.