Singular Gram Matrices and Coefficient Nonuniqueness

Why a Singular Gram Matrix Needs Careful Interpretation

In a kernel model, a function in the span of the observed kernel sections is written as a weighted sum of functions \(k_{x_i}=k(x_i,\cdot)\). The weights are convenient coordinates, but they are not always unique: distinct coefficient vectors can describe the very same function. This happens precisely when the kernel sections are linearly dependent in the RKHS, and it is reflected in a singular Gram matrix.

The distinction matters in optimization and reporting. A numerical routine may return one of several coefficient vectors, while the fitted function and every prediction are identical across those choices. Singularity is therefore a statement about the coordinates, not automatically about the fitted function.

Definition: For inputs \(x_1,\ldots,x_n\) and a positive semidefinite kernel \(k\), the Gram matrix is \(K\in\mathbb{R}^{n\times n}\) with entries \(K_{ij}=k(x_i,x_j)\). For \(\alpha\in\mathbb{R}^n\), its associated kernel expansion is \(f_\alpha=\sum_{i=1}^n\alpha_i k_{x_i}\). The Gram matrix is singular when it has a nonzero null vector, that is, when \(Kv=0\) for some \(v\ne 0\).

A Gram matrix is always positive semidefinite: for every \(v\in\mathbb{R}^n\), \(v^\top K v\ge 0\). In an RKHS \(\mathcal H\) with reproducing kernel \(k\), the reproducing property gives the more informative identity

v^\top K v =\left\|\sum_{i=1}^n v_i k_{x_i}\right\|_{\mathcal H}^{\,2}.

Thus, a null vector records a linear combination of kernel sections whose RKHS norm is zero. Since an RKHS is a space of functions with a genuine norm, that combination is the zero function.

Null Vectors and the Functions They Leave Unchanged

Define the linear map \(T:\mathbb{R}^n\to\mathcal H\) by \(T\alpha=f_\alpha\). The displayed identity says \(v^\top K v=\|Tv\|_{\mathcal H}^2\). It follows that \(Kv=0\) implies \(Tv=0\). Conversely, if \(Tv=0\), then for every \(i\), \( (Kv)_i=\langle k_{x_i},Tv\rangle_{\mathcal H}=0\), so \(Kv=0\). Therefore the null space of \(K\) is exactly the set of coefficient changes that represent the zero function.

Theorem: For any \(\alpha,\beta\in\mathbb{R}^n\), \(f_\alpha=f_\beta\) if and only if \(\alpha-\beta\in\operatorname{null}(K)\). In particular, all coefficient vectors \(\alpha+v\), with \(v\in\operatorname{null}(K)\), represent the same function as \(\alpha\), and give the same predictions at every input.

Proof. Let \(v=\alpha-\beta\). If \(Kv=0\), then \[ \|f_\alpha-f_\beta\|_{\mathcal H}^2 =\|Tv\|_{\mathcal H}^2 =v^\top K v=0, \] so \(f_\alpha=f_\beta\). Conversely, if \(f_\alpha=f_\beta\), then \(Tv=0\), and for every \(i\), \[ (Kv)_i=\sum_{j=1}^n k(x_i,x_j)v_j =\langle k_{x_i},Tv\rangle_{\mathcal H}=0. \] Hence \(Kv=0\). Since equal functions have equal evaluations at every input, their predictions agree everywhere as well. \(\square\)

At the observed inputs, the vector of fitted values is \(K\alpha\), because \(f_\alpha(x_i)=\sum_j K_{ij}\alpha_j\). At a new input \(x\), the prediction is \(\sum_i\alpha_i k(x_i,x)\). If \(v\in\operatorname{null}(K)\), then \(f_v\) is the zero function, so adding \(v\) changes neither expression.

Worked Example: Repeated Inputs Give Nonunique Coefficients

Suppose \(x_1=x_2=x_0\), and let \(k(x_0,x_0)=1\). Then \(k_{x_1}=k_{x_2}=k_{x_0}\), and

K=\begin{pmatrix}1&1\\1&1\end{pmatrix}, \qquad K\begin{pmatrix}1\\-1\end{pmatrix} =\begin{pmatrix}0\\0\end{pmatrix}.

For coefficients \(\alpha=(a,b)^\top\), the represented function is \(f_\alpha=(a+b)k_{x_0}\). Only the sum \(s=a+b\) matters. To see this directly in an objective, consider

J(a,b) =\frac12\big[(1-s)^2+(3-s)^2\big]+s^2.

The final term is the squared RKHS norm, since \(\|s k_{x_0}\|_{\mathcal H}^2=s^2\). Expanding the two squared errors gives \[ J(a,b)=\frac12(1-2s+s^2+9-6s+s^2)+s^2 =2s^2-4s+5=2(s-1)^2+3. \] The minimum occurs at \(s=1\). Thus every pair with \(a+b=1\), such as \((1,0)\) or \((0,1)\), minimizes the objective. Each gives the same function \(k_{x_0}\) and the same fitted value, \(1\), at both copies of the input. The individual coefficients differ, but the fitted function does not.

Dependence Can Occur Without Repeated Inputs

Repeated inputs are an immediate source of dependence, but they are not the only one. For a linear kernel on \(\mathbb R^2\), \(k(x,z)=x^\top z\), the section \(k_x\) is the function \(z\mapsto x^\top z\). If an input vector is a linear combination of others, the corresponding kernel section has the same relation, even when all the inputs are distinct.

Worked Example: Distinct Inputs with Dependent Sections

Take \(x_1=(1,0)\), \(x_2=(0,1)\), and \(x_3=(1,1)\). These are three distinct inputs, and \(x_3=x_1+x_2\). Their Gram matrix and a null vector are

K=\begin{pmatrix} 1&0&1\\ 0&1&1\\ 1&1&2 \end{pmatrix}, \qquad K\begin{pmatrix}1\\1\\-1\end{pmatrix} =\begin{pmatrix}1+0-1\\0+1-1\\1+1-2\end{pmatrix} =\begin{pmatrix}0\\0\\0\end{pmatrix}.

The corresponding function relation is \(k_{x_1}+k_{x_2}-k_{x_3}=0\). For example, \(\alpha=(1,2,0)^\top\) and \(\beta=(2,3,-1)^\top\) differ by \((1,1,-1)^\top\), so they represent the same function. In feature-vector terms, both give the coefficient vector \((1,2)\) for the linear function \(z\mapsto (1,2)^\top z\).

At \(x_*=(2,-1)\), the kernel evaluations against the three inputs are \((2,-1,1)\). The predictions from the two coefficient vectors are \[ 2(1)-1(2)+1(0)=0,\qquad 2(2)-1(3)+1(-1)=0. \] The equality is not specific to \(x_*\): the two expansions are the same function, so they agree at every input.

When the Fitted Function Is Unique

Coefficient nonuniqueness does not by itself make an optimization problem ill-posed. Consider an objective over the kernel span of the form

J(\alpha) =\sum_{i=1}^n \ell_i\big((K\alpha)_i\big) +\frac{\lambda}{2}\alpha^\top K\alpha, \qquad \lambda>0,

where each loss \(\ell_i:\mathbb R\to\mathbb R\) is convex. Both terms depend only on the represented function: the loss uses its fitted values, and \(\alpha^\top K\alpha=\|f_\alpha\|_{\mathcal H}^2\). Consequently, \(J(\alpha+v)=J(\alpha)\) for every \(v\in\operatorname{null}(K)\).

Result: If a minimizer of this objective exists, all minimizing coefficient vectors represent the same function. If \(K\) is singular, adding any null vector to one minimizing coefficient vector gives another minimizing coefficient vector; these vectors nevertheless have identical fitted values and predictions.

Proof. View the objective as a function of \(f\) in the span of the kernel sections: \[ Q(f)=\sum_{i=1}^n \ell_i(f(x_i))+\frac{\lambda}{2}\|f\|_{\mathcal H}^2. \] The loss sum is convex in \(f\), because evaluation \(f\mapsto f(x_i)\) is linear and each \(\ell_i\) is convex. The squared norm is strictly convex: for distinct \(f,g\) and \(0<t<1\), \[ \|tf+(1-t)g\|_{\mathcal H}^2 =t\|f\|_{\mathcal H}^2+(1-t)\|g\|_{\mathcal H}^2 -t(1-t)\|f-g\|_{\mathcal H}^2 <t\|f\|_{\mathcal H}^2+(1-t)\|g\|_{\mathcal H}^2. \] Since \(\lambda>0\), adding the convex loss to the strictly convex penalty leaves \(Q\) strictly convex. Two distinct functions therefore cannot both minimize it. Any two minimizing coefficient vectors must represent the same function, and the theorem above says their difference lies in \(\operatorname{null}(K)\). Conversely, adding a null vector leaves the function and objective unchanged. \(\square\)

Worked Example: A Shifted System Can Have Unique Coefficients

For the repeated-input Gram matrix \(K=\begin{pmatrix}1&1\\1&1\end{pmatrix}\), the unshifted matrix is singular. Add the identity matrix and solve \((K+I)\alpha=y\) for \(y=(1,3)^\top\):

\begin{pmatrix}2&1\\1&2\end{pmatrix} \begin{pmatrix}a\\b\end{pmatrix} =\begin{pmatrix}1\\3\end{pmatrix}.

The equations are \(2a+b=1\) and \(a+2b=3\). Subtracting the first from the second gives \(-a+b=2\), so \(b=a+2\). Substitution gives \(3a+2=1\), hence \(a=-1/3\) and \(b=5/3\). Direct verification yields \(2(-1/3)+5/3=1\) and \(-1/3+2(5/3)=3\). The solution is unique because \(\det(K+I)=2\cdot2-1\cdot1=3\ne0\).

The fitted vector is \(K\alpha=(4/3,4/3)^\top\), since each row of \(K\) sums the two coefficients. This example illustrates that a positive diagonal shift can make a linear system uniquely solvable even when \(K\) itself is singular. It does not make the original kernel sections independent: their coefficient representations of a given function remain nonunique.

Common Pitfalls and Practical Interpretation

A singular Gram matrix should prompt a check of dependencies, not an immediate conclusion that predictions are ambiguous. When inspecting a numerical solution, compare the fitted vector \(K\alpha\) or the function values, rather than interpreting each coefficient as uniquely determined. If a calculation reports different coefficients for the same data configuration, that difference may be a harmless null-space component.

Mistake: “Singular means there is no fitted solution.” Singularity means coefficient coordinates are not uniquely recoverable from the represented function. A minimizing function can still exist and be unique.
Mistake: “Different coefficients must give different predictions.” This is false when their difference lies in \(\operatorname{null}(K)\). Such a difference represents the zero RKHS function, so predictions agree even away from the observed inputs.
Mistake: “Only duplicate inputs cause singularity.” Distinct inputs can have dependent sections, as with linearly dependent vectors under a linear kernel.
Mistake: “A unique solution after adding a diagonal shift proves the Gram matrix was nonsingular.” A shifted matrix can be nonsingular while the original Gram matrix remains singular. The two matrices answer different linear-algebra questions.

The practical distinction is between the identifiable object and its representation. The kernel expansion as a function, its observed fitted values, and all its predictions are invariant to null-space changes in the coefficients. Coefficient-level summaries or algorithms that demand a unique vector need an additional convention or a nonsingular system, but that is separate from whether the fitted function is well defined.

Check Your Understanding

Use the null-space and function-space distinctions to answer these questions.

For a Gram matrix \(K\), what does a nonzero vector \(v\in\operatorname{null}(K)\) say about the associated kernel sections?
If \(\beta=\alpha+v\) with \(Kv=0\), explain why \(K\alpha=K\beta\) and why the two vectors also give the same prediction at an arbitrary input.
How can distinct inputs produce a singular Gram matrix for the linear kernel?
In the repeated-input example, why do all pairs satisfying \(a+b=1\) give the same minimizer?
Why does adding a positive diagonal shift potentially yield a unique solution without changing the fact that the original kernel sections are dependent?