Least Squares

Best fit when there's no exact solution: the normal equations.

The idea

Least squares is the method for treating a system $Ax = b$ that has no exact solution. Such systems are the normal case when the equations come from measurements: with more equations than unknowns, $b$ usually lies outside the column space of $A$ — the set of all vectors of the form $Ax$ — and then no $x$ satisfies every equation.

Least squares asks instead for the $\hat{x}$ that brings $A\hat{x}$ closest to $b$, measuring the error by its squared length: $\text{minimize} \quad \lVert Ax - b \rVert^{2}.$

The column space is a subspace, and the point of a subspace nearest to $b$ is the foot of the perpendicular dropped from $b$. So $A\hat{x}$ is the projection of $b$ onto the column space, as in the figure, and the error $b - A\hat{x}$, the residual, is perpendicular to every column of $A$.

Writing that perpendicularity as $A^{\top}(b - A\hat{x}) = 0$ and rearranging gives the normal equations $A^{\top}A\,\hat{x} = A^{\top}b,$ a square system that always has a solution. Solving it is the whole computation.

Ways to work on it

• Walkthrough. Projection, the residual, and the normal equations A^ A x = A^ b.
• Practice. Solve the normal equation for a best-fit constant.
• Hardest. Build and solve the 2-by-2 normal equations to fit a line.

Not sure where to start? Take the ten-question placement test.