Least-Squares Approximation & the Normal Equations

Many real problems lead to a system $A\mathbf{x}=\mathbf{b}$ with more equations than unknowns (an $n\times m$ matrix $A$ with $n>m$). Measurement noise then usually pushes $\mathbf{b}$ outside the column space, $\mathbf{b}\notin\operatorname{im}(A)$, so no $\mathbf{x}$ satisfies every equation exactly — the system is inconsistent. Rather than give up, we look for the best approximate solution. A least-squares solution (Definition 8.9) is a vector $\hat{\mathbf{x}}\in\mathbb{R}^m$ that minimises the Euclidean error $\|\mathbf{b}-A\hat{\mathbf{x}}\|\le\|\mathbf{b}-A\mathbf{x}\|\qquad\text{for all }\mathbf{x}\in\mathbb{R}^m.$ The name comes from minimising $\|\mathbf{b}-A\mathbf{x}\|^2$, a sum of squares of the residual entries. If the system happens to be consistent, the minimum error is $0$, and the least-squares solutions are exactly the ordinary solutions.

Minimising distance to a subspace has a clean geometric answer. Given $\mathbf{b}\in\mathbb{R}^n$ and a subspace $V\subseteq\mathbb{R}^n$, Theorem 8.12 says the point of $V$ closest to $\mathbf{b}$ is the orthogonal projection $\operatorname{proj}_V\mathbf{b}$: $\|\mathbf{b}-\operatorname{proj}_V\mathbf{b}\|<\|\mathbf{b}-\mathbf{v}\|\qquad\text{for every }\mathbf{v}\in V,\ \mathbf{v}\neq\operatorname{proj}_V\mathbf{b}.$ The proof is one application of Pythagoras: write $\mathbf{b}-\mathbf{v}=(\mathbf{b}-\operatorname{proj}_V\mathbf{b})+(\operatorname{proj}_V\mathbf{b}-\mathbf{v})$. The first piece lies in $V^{\perp}$ and the second in $V$, so they are orthogonal and $\|\mathbf{b}-\mathbf{v}\|^2=\|\mathbf{b}-\operatorname{proj}_V\mathbf{b}\|^2+\|\operatorname{proj}_V\mathbf{b}-\mathbf{v}\|^2$, which is smallest exactly when the last term is $0$. Taking $V=\operatorname{im}(A)$, the best $A\hat{\mathbf{x}}$ is therefore $\operatorname{proj}_{\operatorname{im}(A)}\mathbf{b}$, and the residual $\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to the column space.

Orthogonality of the residual is what we can compute with. Since $\operatorname{im}(A)^{\perp}=\ker(A^{\mathsf{T}})$ (Theorem 8.10), the statement 'the residual is orthogonal to every column of $A$' becomes $A\hat{\mathbf{x}}=\operatorname{proj}_{\operatorname{im}(A)}\mathbf{b}\iff\mathbf{b}-A\hat{\mathbf{x}}\in\ker(A^{\mathsf{T}})\iff A^{\mathsf{T}}(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0}\iff A^{\mathsf{T}}A\hat{\mathbf{x}}=A^{\mathsf{T}}\mathbf{b}.$ This last system is the normal equation, and Theorem 8.13 says its exact solutions are precisely the least-squares solutions of $A\mathbf{x}=\mathbf{b}$ — and it is always consistent, even when the original system is not. The solution is unique if and only if $\ker(A)=\{\mathbf{0}\}$ (that is, $A$ has linearly independent columns); then $A^{\mathsf{T}}A$ is invertible (Corollary 8.1, via $\ker(A^{\mathsf{T}}A)=\ker(A)$ from Theorem 8.11) and $\hat{\mathbf{x}}=(A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}\mathbf{b}.$

The classic application is a line of best fit. To fit $y=mx+c$ to data $(x_1,y_1),\dots,(x_n,y_n)$, we would like $mx_i+c=y_i$ for every $i$ — the system $\underbrace{\begin{bmatrix}x_1&1\\\vdots&\vdots\\x_n&1\end{bmatrix}}_{A}\begin{bmatrix}m\\c\end{bmatrix}=\underbrace{\begin{bmatrix}y_1\\\vdots\\y_n\end{bmatrix}}_{\mathbf{b}}.$ With more than two non-identical points this is over-determined and inconsistent, so we solve the normal equation $A^{\mathsf{T}}A\,[\,m\ \ c\,]^{\mathsf{T}}=A^{\mathsf{T}}\mathbf{b}$ instead; the unique pair $(m,c)$ minimises the total squared vertical error $\sum_i(y_i-mx_i-c)^2$. The same recipe fits any model linear in its parameters — a parabola $y=a+bx+cx^2$ just uses columns $1,\,x,\,x^2$. Finally, when $A$ has independent columns, Theorem 8.14 packages the fitted values as a projection, $\operatorname{proj}_{\operatorname{im}(A)}\mathbf{b}=A(A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}\mathbf{b},$ a projection formula valid for any basis (the columns of $A$), generalising $P=QQ^{\mathsf{T}}$ for an orthonormal basis.