Least-Squares and Solution Uniqueness

I recently was in discussion and could not answer off the top for what to me sounded like a simple question on linear algebra and least squares fitting. So I decided to do some reading and write up a short post on the topic.The question was: is the fitted parameter vector guaranteed to be unique?

For ordinary least squares, the answer is not always. If the design matrix $\mathbf{A}$ has linearly dependent columns, then different parameter vectors $\mathbf{c}$ can produce the same predictions. A common fix is ridge regularization. When the ridge is added with a positive value, the answer becomes yes. The addition of regularization makes the normal-equation matrix positive definite. Positive definite matrices imply invertibility of that linear system, and consequently make the least-squares objective strictly convex, so a unique global minimizer exists.

Just restating it so I remember, when you add a constant diagonal term $\lambda\mathbf{I}$ into the normal-equation matrix (see eq.\ref{eq:H}), you make it positive definite and therefore invertible, which means uniqueness.

The Regularized Problem

Consider the regularized least-squares objective below where we want to find the set of optimal parameters $\mathbf{c}$:

$$ \begin{align} J(\mathbf{c}) &= \left| \mathbf{W}^{1/2} (\mathbf{A}\mathbf{c} - \mathbf{b}) \right|_{2}^{2} \nonumber\\ &\quad + \underbrace{\lambda \left| \mathbf{c} \right|_{2}^{2}}_{\text{ridge regularization term}} \nonumber\\ &\quad + \underbrace{\gamma \left| \mathbf{D}\mathbf{c} \right|_{2}^{2}}_{\text{roughness regularization term}}, \label{eq:objective} \end{align} $$

where $\mathbf{A}$ is the design matrix, $\mathbf{c}$ contains the fitted coefficients, $\mathbf{W}$ is a symmetric positive-semidefinite weight matrix (typically diagonal with nonnegative entries), and $\mathbf{D}$ is a discrete derivative / roughness operator (first- or second-difference, depending on whether one penalizes slope or curvature). Taking the gradient of eq.\ref{eq:objective} and setting it equal to zero yields the normal equation:

$$ \begin{equation} \mathbf{H}\mathbf{c}=\mathbf{A}^{T}\mathbf{W}\mathbf{b}, \label{eq:normal} \end{equation} $$

with $\mathbf{H}$ being defined as:

$$ \begin{equation} \mathbf{H}=\mathbf{A}^{T}\mathbf{W}\mathbf{A}+\lambda\mathbf{I}+\gamma\mathbf{D}^{T}\mathbf{D}. \label{eq:H} \end{equation} $$

The whole question of uniqueness therefore reduces to whether $\mathbf{H}$ is positive definite.

Why is $\mathbf{H}$ Positive Definite?

Let's try to understand this geometrically. Take any nonzero vector $\mathbf{z} = (z_1, z_2, \ldots)$. If we want to see whether a matrix like $\mathbf{H}$ is positive definite, we look at its so-called quadratic form $\mathbf{z}^{T}\mathbf{H}\mathbf{z}$, with $\mathbf{H}$ from eq.\ref{eq:H}. Expanding that definition gives

$$ \begin{equation} \mathbf{z}^{T}\mathbf{H}\mathbf{z}=\left|\mathbf{W}^{1/2}\mathbf{A}\mathbf{z}\right|_{2}^{2}+\lambda\left|\mathbf{z}\right|_{2}^{2}+\gamma\left|\mathbf{D}\mathbf{z}\right|_{2}^{2}. \label{eq:quad} \end{equation} $$

This just means we plug $\mathbf{z}$ into eq.\ref{eq:H} (so, multiply $\mathbf{z}$ by $\mathbf{H}$, then by $\mathbf{z}$ again) and rewrite the result as a sum of squared norms. If the right-hand side of eq.\ref{eq:quad} is always greater than zero for any nonzero vector $\mathbf{z}$, then $\mathbf{H}$ is positive definite.

Figure 1. Equal-cost valleys without ridge (vertical lines; many (z1,z2) pairs share one cost) become closed equal-cost contours with ridge (cost grows even along z1=0).

To try and geometrically visualize eq.\ref{eq:quad}, Figure 1 animates the components of a coefficient vector $\mathbf{z}=(z_{1},z_{2})$. Without ridge, equal-cost contours of the toy form $\mathbf{z}^{T}\mathbf{H}_{0}\mathbf{z}=z_{1}^{2}$ are vertical lines. This means if you fix $z_{1}$ and slide $z_{2}$, the cost does not change. Many different pairs $(z_{1},z_{2})$ therefore share the same cost (i.e., are degenerate solutions). The worst valley is $z_{1}=0$, where $\mathbf{A}\mathbf{z}=\mathbf{0}$ and the cost is zero for every $z_{2}$. When we use regularization (i.e., a ridge), the cost becomes $z_{1}^{2}+\lambda z_{2}^{2}$ and the contours close into a bowl. Even along $z_{1}=0$ one pays $\lambda z_{2}^{2}>0$ unless $\mathbf{z}=\mathbf{0}$ ¹. In jargon, the line $z_{1}=0$ is the null space of $\mathbf{A}$. Therefore,

$$ \mathbf{z}^{T}\mathbf{H}\mathbf{z}>0\qquad\text{for every }\mathbf{z}\neq\mathbf{0}, $$

which means

$$ \mathbf{H}\underbrace{\succ}_{\text{is positive definite}}0. $$

This immediately means that $\mathbf{H}$ is invertible and therefore eq.\ref{eq:normal} has exactly one solution (a unique critical point). Another note is that the Hessian of eq.\ref{eq:objective} is $2\mathbf{H}$, which is also positive definite, so $J$ is strictly convex and that critical point is the unique global minimizer [1].

Where the guarantee actually comes from

The roughness term $\mathbf{D}^{T}\mathbf{D}$ is generally positive semidefinite, not positive definite, because a discrete derivative operator normally has a null space (for example constant vectors for a first-difference $\mathbf{D}$). Roughness regularization alone does not automatically guarantee uniqueness. The unconditional guarantee here comes from the positive ridge term $\lambda\mathbf{I}$; the roughness term adds smoothness without changing that conclusion. Data weights and $\gamma$ do not carry the uniqueness guarantee either.

Closing things out, the compact mathematical statement is then:

$$ \begin{align} \lambda>0 &\Longrightarrow\mathbf{H}\succ0 \nonumber\\ &\Longrightarrow J(\mathbf{c})\text{ is strictly convex} \nonumber\\ &\Longrightarrow\mathbf{c}^{*}\text{ is the unique global minimizer}. \end{align} $$

Punchline

Invertibility of $\mathbf{H}$ is what makes the linear system have one solution. Positive definiteness is what makes $J$ strictly convex, so that solution is the unique global minimizer ... the existence of $\mathbf{H}^{-1}$ is a consequence, not the cause. Numerically you would probably still solve eq.\ref{eq:normal} as a linear system (e.g., via Cholesky decomposition) rather than explicitly forming $\mathbf{H}^{-1}$.

Footnotes

---

1. Same cost is not the same thing as same length $|\mathbf{z}|_{2}$. ↩

References

[1] S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. https://doi.org/10.1017/CBO9780511804441.

Reuse and Attribution