Least squares is both a geometric projection problem and a basic numerical subroutine for data fitting, inverse problems, and discretized equations.
Linear least squares
Definition. The linear least-squares problem seeks \(x\) minimizing \(\|Ax-b\|_2\). If \(A\) has full column rank, the solution is unique and satisfies the normal equations \(A^\top A x=A^\top b\).
Orthogonal projection
Proposition. The residual \(r=b-A\widehat x\) of a least-squares solution is orthogonal to the column space of \(A\). Thus least squares computes the orthogonal projection of \(b\) onto \(\operatorname{col}(A)\).
Normal equations warning
Theorem. Solving least squares through \(A^\top A\) squares the condition number: \(\kappa(A^\top A)=\kappa(A)^2\). QR or SVD methods are therefore preferred when numerical accuracy matters.
Rank deficiency
Definition. When \(A\) is rank deficient or nearly rank deficient, the minimum-norm least-squares solution is expressed by the pseudoinverse \(A^+b\). Truncated SVD gives a regularized version by discarding small singular directions.
Weighted and generalized least squares
Remark. Weighted least squares changes the geometry of the residual norm. In statistical problems this geometry is often determined by the covariance of the noise, but the numerical question remains how to solve the resulting system stably.
Projection and normal equations
For full-column-rank \(A\in\mathbb R^{m\times n}\), \[ \widehat x=\arg\min_x\|Ax-b\|_2 \] is characterized by \[ A^\top(A\widehat x-b)=0. \] Thus \(A\widehat x\) is the orthogonal projection of \(b\) onto \(\operatorname{col}(A)\).
Theorem. If \(A=QR\) is reduced QR, \[ \widehat x=R^{-1}Q^\top b,\qquad r=b-A\widehat x=(I-QQ^\top)b. \]
Proof. Orthogonal invariance gives \[ \|Ax-b\|_2^2 =\|Rx-Q^\top b\|_2^2+\|(I-QQ^\top)b\|_2^2. \] The first term is uniquely minimized at \(Rx=Q^\top b\).
Why normal equations can lose accuracy
Forming \(A^\top A\) squares the spectral condition number: \[ \kappa_2(A^\top A)=\kappa_2(A)^2. \] Cholesky on the normal equations can therefore lose roughly twice as many digits as QR. QR is the standard stable method; SVD is preferable when rank is uncertain.
Rank deficiency and minimum norm
With SVD \(A=U\Sigma V^\top\), \[ A^\dagger=V\Sigma^\dagger U^\top, \qquad x^\dagger=A^\dagger b \] is the unique least-squares solution of minimum Euclidean norm. Components along small singular values are amplified by \(1/\sigma_j\), exposing both ill-conditioning and the need for regularization.
Statistical covariance and leverage
In \(b=Ax+\varepsilon\), \(E\varepsilon=0\), \(\operatorname{Cov}(\varepsilon)=\sigma^2I\), \[ \operatorname{Cov}(\widehat x)=\sigma^2(A^\top A)^{-1}. \] The hat matrix \(H=A(A^\top A)^{-1}A^\top=QQ^\top\) has leverage scores \(h_{ii}\). Large leverage marks observations that strongly affect the fitted subspace. Computing \(H\) explicitly is unnecessary; row norms of \(Q\) give its diagonal.
Regularized least squares
Tikhonov regularization solves \[ \min_x\|Ax-b\|_2^2+\lambda\|Lx\|_2^2, \] equivalently the augmented system \[ \min_x \left\| \begin{pmatrix}A\\\sqrt\lambda L\end{pmatrix}x -\begin{pmatrix}b\\0\end{pmatrix} \right\|_2. \] Solving the augmented problem by QR avoids forming \(A^\top A+\lambda L^\top L\) and retains a clean backward-error analysis.