Least squares
Real data rarely fit a model exactly. Least squares finds the best approximate solution of an inconsistent system, the foundation of regression and data fitting.
Inconsistent systems
When \(A\mathbf{x} = \mathbf{b}\) has no solution, as with more equations than unknowns from noisy measurements, we seek \(\hat{\mathbf{x}}\) making \(A\hat{\mathbf{x}}\) as close as possible to \(\mathbf{b}\): minimising \(\|\mathbf{b} - A\mathbf{x}\|\), equivalently the sum of squared errors. The method was published by Adrien-Marie Legendre in 1805 and developed by Carl Friedrich Gauss, who used it to predict the orbit of the asteroid Ceres in 1801.
Geometry of least squares
\(A\mathbf{x}\) always lies in Col A. The closest point of Col A to \(\mathbf{b}\) is the projection \(\hat{\mathbf{b}}\), so the least-squares solution satisfies \(A\hat{\mathbf{x}} = \hat{\mathbf{b}}\). The residual \(\mathbf{b} - A\hat{\mathbf{x}}\) is orthogonal to every column of A.
The normal equations
Orthogonality of the residual to A's columns means \(A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}\), giving the normal equations \(A^TA\hat{\mathbf{x}} = A^T\mathbf{b}\). If A's columns are independent, \(A^TA\) is invertible and \(\hat{\mathbf{x}} = (A^TA)^{-1}A^T\mathbf{b}\) is unique.
Fitting a line
To fit \(y = \beta_0 + \beta_1x\) to data points \((x_i, y_i)\), build the design matrix X with a column of 1s and a column of the \(x_i\), and the observation vector \(\mathbf{y}\). The least-squares coefficients solve \(X^TX\boldsymbol{\beta} = X^T\mathbf{y}\). This is ordinary least-squares linear regression, used across science, economics, and machine learning.
Beyond straight lines
Least squares fits any model that is linear in its parameters: polynomials (columns 1, x, x^2, ...), several predictors (multiple regression), or sums of known functions such as sines and cosines for seasonal data. The model can be non-linear in x as long as it is linear in the unknown coefficients.
Numerical methods
Forming \(A^TA\) squares the condition number, which can lose accuracy. Software instead uses the QR factorisation, solving \(R\hat{\mathbf{x}} = Q^T\mathbf{b}\), or the singular value decomposition for rank-deficient problems. Regularisation such as ridge regression, minimising \(\|\mathbf{b} - A\mathbf{x}\|^2 + \lambda\|\mathbf{x}\|^2\), stabilises ill-conditioned problems and reduces overfitting.
Interpreting the fit
The residuals show how well the model fits; plotting them reveals patterns the model missed. The coefficient of determination, R^2, gives the fraction of variation explained. Least squares is sensitive to outliers, since squaring magnifies large errors, so robust methods are used when data contain extreme points.
Worked example
Fit a line to (0, 1), (1, 3), (2, 4). With \(X\) rows (1, 0), (1, 1), (1, 2): \(X^TX = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}\) and \(X^T\mathbf{y} = (8, 11)\). Solving \(3\beta_0 + 3\beta_1 = 8\) and \(3\beta_0 + 5\beta_1 = 11\) gives \(\beta_1 = 1.5\) and \(\beta_0 = \frac{8 - 4.5}{3} = \frac{7}{6}\). The line is \(y = \frac{7}{6} + 1.5x\); its residuals \(-\frac{1}{6}, \frac{1}{3}, -\frac{1}{6}\) sum to zero.
Key takeaways
Least squares minimises ||b - Ax||, the sum of squared errors, for inconsistent systems; Legendre published it in 1805 and Gauss used it for Ceres. The best Ax is the projection of b onto Col A, with residual orthogonal to A's columns. This gives the normal equations A^T A x-hat = A^T b, with a unique solution when columns are independent. Linear regression uses a design matrix with a column of 1s. Any model linear in its parameters can be fitted. Software uses QR or SVD rather than forming A^T A; ridge regression regularises. Residual plots and R^2 assess fit; outliers can distort results.
Flashcard
Minimises ||b - Ax||
Check your understanding
Why is the least-squares residual b - A x-hat orthogonal to every column of A?
