Least-Squares Problems

Over-determined systems — more equations than unknowns, built from noisy measurements — usually have no exact solution. The coefficient matrix $A$ maps ${\mathbb{R}}^n$ onto the subspace $\mathrm{Col}A$, and the target $\mathbf{b}$ typically lies outside it, so no exact solution exists. The practical question is which $\mathbf{x}$ makes $A\mathbf{x}$ closest to $\mathbf{b}$, and the best-approximation theorem answers it: project $\mathbf{b}$ onto $\mathrm{Col}A$.

The least-squares problem

The name records that $\Vert \mathbf{b}-A\mathbf{x}\Vert$ is the square root of a sum of squares, so minimizing it minimizes the total squared error. No matter what $\mathbf{x}$ is chosen, $A\mathbf{x}$ lands somewhere in $\mathrm{Col}A$. The task is to make that point the one in $\mathrm{Col}A$ nearest to $\mathbf{b}$.

The normal equations

Let $\hat{\mathbf{b}}={\mathrm{proj}}_{\mathrm{Col}A}\mathbf{b}$. It is in $\mathrm{Col}A$, so $A\mathbf{x}=\hat{\mathbf{b}}$ is consistent and has a solution $\hat{\mathbf{x}}$. Because $\hat{\mathbf{b}}$ is the closest point of $\mathrm{Col}A$ to $\mathbf{b}$, this $\hat{\mathbf{x}}$ minimizes $\Vert \mathbf{b}-A\mathbf{x}\Vert$ and so is a least-squares solution.

The residual $\mathbf{b}-\hat{\mathbf{b}}=\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to $\mathrm{Col}A$, hence orthogonal to every column of $A$. If ${\mathbf{a}}_j$ is a column, then ${\mathbf{a}}_j\cdot (\mathbf{b}-A\hat{\mathbf{x}})=0$, i.e. ${\mathbf{a}}_j^{\top }(\mathbf{b}-A\hat{\mathbf{x}})=0$. Stacking these over all columns is the single matrix equation $A^{\top }(\mathbf{b}-A\hat{\mathbf{x}})=0$, which rearranges to

The forward direction is the derivation above. Conversely, if $\hat{\mathbf{x}}$ satisfies the normal equations, then $\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to the rows of $A^{\top }$, hence to the columns of $A$, hence to all of $\mathrm{Col}A$. So $\mathbf{b}=A\hat{\mathbf{x}}+(\mathbf{b}-A\hat{\mathbf{x}})$ is an orthogonal decomposition, and by uniqueness $A\hat{\mathbf{x}}$ must equal the projection $\hat{\mathbf{b}}$ — making $\hat{\mathbf{x}}$ a least-squares solution. The normal equations convert a minimization into a square linear system.

Non-unique least-squares solutions

When the columns of $A$ are dependent, $A\mathbf{x}=\hat{\mathbf{b}}$ has free variables and the least-squares solutions form a whole family.

Such matrices appear in the analysis-of-variance problems of statistics, where the columns encode overlapping group memberships.

Uniqueness of the least-squares solution

The projection $\hat{\mathbf{b}}$ is unique, but the $\hat{\mathbf{x}}$ producing it need not be. Uniqueness is governed by the columns of $A$.

The equivalence rests on the fact that $\mathrm{Nul}(A^{\top }A)=\mathrm{Nul}A$: if $A^{\top }A\mathbf{x}=0$, then ${\mathbf{x}}^{\top }{A}^{\top }A\mathbf{x}=\Vert A\mathbf{x}{\Vert }^2=0$, so $A\mathbf{x}=0$, and the reverse is obvious. Independent columns thus make $A^{\top }A$ have trivial null space, hence invertible. The closed form $(A^{\top }A{)}^{-1}{A}^{\top }\mathbf{b}$ is convenient for a $2\times 2$ system but is not the recommended route for larger or ill-conditioned problems.

When the columns are orthogonal, no inverse is needed at all: the projection is the sum of one-dimensional projections, and the weights are the least-squares solution directly. For $A=[{\mathbf{a}}_1{\mathbf{a}}_2]$ with orthogonal columns,

Matrices with orthogonal columns arise routinely in the regression models where centering the data makes the design matrix's columns orthogonal by construction.

The least-squares error

Once $\hat{\mathbf{x}}$ is found, the quality of the fit is the distance from $\mathbf{b}$ to its approximation.

For the worked example, $A\hat{\mathbf{x}}=(4,4,3)$, so $\mathbf{b}-A\hat{\mathbf{x}}=(-2,-4,8)$ and the error is $\sqrt{4+16+64}=\sqrt{84}$. No $\mathbf{x}$ can bring $A\mathbf{x}$ within $\sqrt{84}$ of $\mathbf{b}$; the residual is the leg of the right triangle from $\mathbf{b}$ down to $\mathrm{Col}A$. An error of zero means $\mathbf{b}$ was already in $\mathrm{Col}A$ and the original system was consistent.

The QR route

The formula $\hat{\mathbf{x}}=(A^{\top }A{)}^{-1}{A}^{\top }\mathbf{b}$ can amplify rounding error: forming $A^{\top }A$ squares the sensitivity of the problem. When the columns of $A$ are independent, the QR factorization gives a more reliable path.

With $A=QR$, the projection of $\mathbf{b}$ onto $\mathrm{Col}A=\mathrm{Col}Q$ is $Q{Q}^{\top }\mathbf{b}$ (projection onto an orthonormal basis). Then $A\hat{\mathbf{x}}=QR{R}^{-1}{Q}^{\top }\mathbf{b}=Q{Q}^{\top }\mathbf{b}=\hat{\mathbf{b}}$, so $\hat{\mathbf{x}}$ is the least-squares solution. In practice one does not invert $R$; since $R$ is upper triangular, the system

is solved by back-substitution, which is faster and more accurate than computing $R^{-1}$.

Summary

The least-squares solution is a projection: $A\hat{\mathbf{x}}$ is the foot of the perpendicular from $\mathbf{b}$ to $\mathrm{Col}A$, and the normal equations are the algebraic statement that the residual is orthogonal to every column. Fitting lines, polynomials, and surfaces to data applies the same machinery with $A$ a design matrix.¹