Least Squares

Real data rarely fit a model exactly. In Algebra 1 you drew a line of fit and looked at residuals; here we find the best line exactly. In matrix language: $A\mathbf{x} = \mathbf{b}$ has no solution, so we look for the $\hat{\mathbf{x}}$ that makes $A\hat{\mathbf{x}}$ as close as possible to $\mathbf{b}$. Projection gives the answer.

Key idea

A least-squares solution of $A\mathbf{x} = \mathbf{b}$ minimizes $\lVert\mathbf{b} - A\mathbf{x}\rVert$. The least-squares solutions are exactly the solutions of the normal equations $$A^{T}A\hat{\mathbf{x}} = A^{T}\mathbf{b}.$$ When the columns of $A$ are independent, $\hat{\mathbf{x}} = (A^{T}A)^{-1}A^{T}\mathbf{b}$ is unique.

Why it works

$A\mathbf{x}$ ranges over $\operatorname{Col} A$, so the closest $A\mathbf{x}$ to $\mathbf{b}$ is the projection $\hat{\mathbf{b}}$ of $\mathbf{b}$ onto $\operatorname{Col} A$. The leftover $\mathbf{b} - A\hat{\mathbf{x}}$ must be orthogonal to $\operatorname{Col} A$, so it lies in $(\operatorname{Col} A)^{\perp} = \operatorname{Nul} A^{T}$ (from orthogonal complements): $A^{T}(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$. Rearranged, that is $A^{T}A\hat{\mathbf{x}} = A^{T}\mathbf{b}$. No orthogonal basis is needed: the normal equations do the projection for us.

$\mathbf{b}$ is not in $\operatorname{Col} A$ (the plane). The best we can do is $A\hat{\mathbf{x}}$, its projection; the residual $\mathbf{b} - A\hat{\mathbf{x}}$ is perpendicular to the plane.

Worked example: An inconsistent system

Find the least-squares solution of $A\mathbf{x} = \mathbf{b}$ with $A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 3 \end{bmatrix}$, $\mathbf{b} = \begin{bmatrix} 3 \\ 0 \\ 8 \end{bmatrix}$.

$A^{T}A = \begin{bmatrix} 3 & 4 \\ 4 & 10 \end{bmatrix}$ and $A^{T}\mathbf{b} = \begin{bmatrix} 11 \\ 24 \end{bmatrix}$.
Solve $\begin{bmatrix} 3 & 4 \\ 4 & 10 \end{bmatrix}\hat{\mathbf{x}} = \begin{bmatrix} 11 \\ 24 \end{bmatrix}$: the determinant is $30 - 16 = 14$, and $\hat{\mathbf{x}}$ $= \frac{1}{14}\begin{bmatrix} 10 & -4 \\ -4 & 3 \end{bmatrix}\begin{bmatrix} 11 \\ 24 \end{bmatrix}$ $= \begin{bmatrix} 1 \\ 2 \end{bmatrix}$.
$A\hat{\mathbf{x}} = \begin{bmatrix} 1 \\ 3 \\ 7 \end{bmatrix}$, residual $\mathbf{b} - A\hat{\mathbf{x}} = \begin{bmatrix} 2 \\ -3 \\ 1 \end{bmatrix}$. Check: it is orthogonal to both columns ($2 - 3 + 1 = 0$ and $0 - 3 + 3 = 0$).
Least-squares error: $\sqrt{4 + 9 + 1} = \sqrt{14}$.

Answer: $\hat{\mathbf{x}} = (1, 2)$

Worked example: Fitting a line

Find the least-squares line $y = \beta_0 + \beta_1x$ through $(0, 1)$, $(1, 1)$, $(2, 3)$, $(3, 3)$.

Each point gives an equation $\beta_0 + \beta_1x_i = y_i$. The design matrix has a column of $1$s and a column of $x$'s: $X = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$, $\mathbf{y} = \begin{bmatrix} 1 \\ 1 \\ 3 \\ 3 \end{bmatrix}$.
$X^{T}X = \begin{bmatrix} 4 & 6 \\ 6 & 14 \end{bmatrix}$ and $X^{T}\mathbf{y} = \begin{bmatrix} 8 \\ 16 \end{bmatrix}$.
Solve: determinant $56 - 36 = 20$; $\boldsymbol{\beta}$ $= \frac{1}{20}\begin{bmatrix} 14 & -6 \\ -6 & 4 \end{bmatrix}\begin{bmatrix} 8 \\ 16 \end{bmatrix}$ $= \begin{bmatrix} \frac{4}{5} \\ \frac{4}{5} \end{bmatrix}$.
The line is $y = 0.8 + 0.8x$. Its residuals $(0.2, -0.6, 0.6, -0.2)$ add up to $0$, as they always do when the model has an intercept.

Answer: $y = 0.8 + 0.8x$

The least-squares line makes the total area of the residual squares as small as possible. Drag a point and watch it refit.

Common mistake

Trying to solve $A\mathbf{x} = \mathbf{b}$ directly when it is inconsistent, for example by row reducing $[\,A \mid \mathbf{b}\,]$, finding a $0 = c$ row, and stopping, or by solving just two of the equations and ignoring the rest. Multiply by $A^{T}$ first and solve the normal equations. Check: the residual $\mathbf{b} - A\hat{\mathbf{x}}$ must be orthogonal to every column of $A$.

This is exactly ordinary least squares (OLS) in statistics and economics. With many explanatory variables, the design matrix $X$ gets one column per variable, and the estimate is $\hat{\boldsymbol{\beta}} = (X^{T}X)^{-1}X^{T}\mathbf{y}$. The Teddy Rook Book Econometrics course builds on this formula, starting with fitting a line and multiple regression.

Least Squares

Practice

Builds on

Leads to

Sources and further reading