← Back to Linear Algebra

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

Least-squares solution

Minimises ||b - Ax||

Best approximation.

Check your understanding

Why is the least-squares residual b - A x-hat orthogonal to every column of A?

← Previous lesson Next lesson →