Existence Of Least-Squares Solutions

When an Exact Solution Does Not Exist

A system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) may have no exact solution: there may be no choice of \(\mathbf{x}\) that makes the product \(\mathbf{A}\mathbf{x}\) equal to \(\mathbf{b}\). Least squares replaces exact equality with a minimization question. Among all vectors the matrix can produce, which one is closest to \(\mathbf{b}\)? If that closest vector can be written as \(\mathbf{A}\widehat{\mathbf{x}}\), then \(\widehat{\mathbf{x}}\) is a least-squares solution.

Throughout, \(\mathbf{A}\in\mathbb{R}^{m\times n}\) and \(\mathbf{b}\in\mathbb{R}^m\). The column space of \(\mathbf{A}\), written \(\operatorname{Col}\mathbf{A}\), is the set of all linear combinations of its columns. Thus \(\operatorname{Col}\mathbf{A}=\{\mathbf{A}\mathbf{x}:\mathbf{x}\in\mathbb{R}^n\}\). The residual at \(\mathbf{x}\) is \(\mathbf{b}-\mathbf{A}\mathbf{x}\); its norm measures the error in the fit.

The vectors \(\mathbf{A}\mathbf{x}\) range over \(\operatorname{Col}\mathbf{A}\), not over all of \(\mathbb{R}^m\) in general. Therefore, the least-squares question is exactly the question of finding a closest vector in \(\operatorname{Col}\mathbf{A}\) to \(\mathbf{b}\). That subspace is finite-dimensional, so the orthogonal projection of \(\mathbf{b}\) onto it exists. The key point for existence is that this projected vector is itself a matrix output: it belongs to \(\operatorname{Col}\mathbf{A}\), so at least one vector of coefficients produces it.

The Projection Argument

Recall that vectors \(\mathbf{u}\) and \(\mathbf{v}\) in \(\mathbb{R}^m\) are orthogonal when \(\mathbf{u}\cdot\mathbf{v}=0\). The orthogonal projection of \(\mathbf{b}\) onto a subspace \(S\) is the vector \(\mathbf{p}\in S\) for which \(\mathbf{b}-\mathbf{p}\) is orthogonal to every vector in \(S\). For a finite-dimensional subspace, such a vector can be constructed using an orthonormal basis: if \(\mathbf{q}_1,\dots,\mathbf{q}_r\) is an orthonormal basis of \(S\), then \(\mathbf{p}=\sum_{i=1}^r(\mathbf{b}\cdot\mathbf{q}_i)\mathbf{q}_i\). If \(S=\{\mathbf{0}\}\), the basis is empty and the sum is \(\mathbf{0}\).

Proof. Set \(S=\operatorname{Col}\mathbf{A}\). This is a finite-dimensional subspace of \(\mathbb{R}^m\). If \(S=\{\mathbf{0}\}\), let \(\mathbf{p}=\mathbf{0}\). Otherwise, choose a basis \(\mathbf{v}_1,\dots,\mathbf{v}_r\) of \(S\). Applying the Gram-Schmidt construction to this basis gives an orthonormal basis \(\mathbf{q}_1,\dots,\mathbf{q}_r\): at step \(k\), subtract from \(\mathbf{v}_k\) its components along the already constructed \(\mathbf{q}_i\), then normalize the result. The result before normalization is nonzero, since if it were zero then \(\mathbf{v}_k\) would be a linear combination of the preceding basis vectors, contradicting independence.

For \(S\ne\{\mathbf{0}\}\), define \(\mathbf{p}=\sum_{i=1}^r(\mathbf{b}\cdot\mathbf{q}_i)\mathbf{q}_i\); for \(S=\{\mathbf{0}\}\), use \(\mathbf{p}=\mathbf{0}\). In either case \(\mathbf{p}\in S\). In the nonzero case, for each \(j\), orthonormality gives \(\mathbf{q}_j\cdot(\mathbf{b}-\mathbf{p})=\mathbf{q}_j\cdot\mathbf{b}-\sum_{i=1}^r(\mathbf{b}\cdot\mathbf{q}_i)(\mathbf{q}_j\cdot\mathbf{q}_i)=\mathbf{b}\cdot\mathbf{q}_j-\mathbf{b}\cdot\mathbf{q}_j=0\). Since the \(\mathbf{q}_j\) span \(S\), this means \(\mathbf{b}-\mathbf{p}\) is orthogonal to every vector in \(S\). In the zero-subspace case, \(\mathbf{b}-\mathbf{p}=\mathbf{b}\) is orthogonal to the only vector in \(S\), namely \(\mathbf{0}\).

For any \(\mathbf{x}\in\mathbb{R}^n\), we have \(\mathbf{A}\mathbf{x}\in S\), and therefore \(\mathbf{p}-\mathbf{A}\mathbf{x}\in S\). The two terms in \(\mathbf{b}-\mathbf{A}\mathbf{x}=(\mathbf{b}-\mathbf{p})+(\mathbf{p}-\mathbf{A}\mathbf{x})\) are orthogonal. Expanding the dot product of this sum with itself gives \(\|\mathbf{b}-\mathbf{A}\mathbf{x}\|^2=\|\mathbf{b}-\mathbf{p}\|^2+\|\mathbf{p}-\mathbf{A}\mathbf{x}\|^2\geq\|\mathbf{b}-\mathbf{p}\|^2\). Because \(\mathbf{p}\in S=\operatorname{Col}\mathbf{A}\), the definition of column space gives at least one \(\widehat{\mathbf{x}}\in\mathbb{R}^n\) with \(\mathbf{A}\widehat{\mathbf{x}}=\mathbf{p}\). For this choice the second squared norm is zero, so it attains the minimum residual norm. \(\square\)

The proof separates two jobs. Projection identifies the closest attainable output \(\mathbf{p}\); membership in the column space guarantees that some coefficient vector produces that output. It does not claim that this coefficient vector is unique. The minimum value is determined by the projection, while more than one coefficient vector can sometimes produce the same projected vector.

Worked Projection Examples

Common Mistake: Demanding an Exact Fit

In the last example, a mistaken approach is to conclude that no least-squares solution exists because the equation \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has no exact solution. Indeed, every output \(\mathbf{A}\mathbf{x}=(t,0,t)^{\top}\) has second coordinate \(0\), whereas \(\mathbf{b}\) has second coordinate \(1\). Thus no output equals \(\mathbf{b}\). But this only rules out an exact solution; it does not rule out minimizing the residual. The calculation above shows that \(t=1\) gives the minimum squared residual \(3\), attained by \(\widehat{\mathbf{x}}=(1,0)^{\top}\).

A useful check is to keep the two questions separate. An exact solution requires \(\mathbf{b}\in\operatorname{Col}\mathbf{A}\). A least-squares solution requires a coefficient vector whose output is closest to \(\mathbf{b}\) among all vectors in \(\operatorname{Col}\mathbf{A}\). If \(\mathbf{b}\) already lies in the column space, its projection is \(\mathbf{b}\) itself and the minimum residual is zero. If it does not, the projection still exists, and its residual need not be zero.

Existence does not imply uniqueness. The projection onto the column space is a single vector, but different coefficient vectors can map to that same vector when the columns are dependent. The theorem guarantees at least one coefficient vector in all cases; determining when it is unique is a separate question.