Least squares

Three points, and no straight line passes through all three. Which line comes closest? Watch the answer appear twice.

No line passes through all three

A line $y=c_0+c_1t$ through the three points $(0,1)$, $(1,3)$ and $(2,2)$ would need

Three equations, two unknowns, and no solution: the first two give $c_0=1$, $c_1=2$, and then the third says $5=2$. In the language of Two pictures of a linear system, $\mathbf{y}$ is not a mix of the columns of $\mathbf{A}$.

So we ask for less. Every line misses each point by some amount, measured straight up or down. We choose the line that makes the sum of the squared misses as small as possible:

That is the least squares line. The misses are measured vertically, because the error is in the heights, not in $t$. The fitted line is not the one with the shortest right-angle distances to the points.

The fit is a shadow

Now the right panel. The three heights are one point $\mathbf{y}$ in space. Every line $c_0+c_1t$ gives three heights $\mathbf{A}\mathbf{x}=c_0\,(1,1,1)+c_1\,(0,1,2)$, and all such points form a plane, the column space $C(\mathbf{A})$. The sum of the squared misses is the squared distance from $\mathbf{y}$ to one of those points.

So the best line is the nearest point of the plane to $\mathbf{y}$. That is the projection of Projections: drop from $\mathbf{y}$ at a right angle. Its weights $\hat{\mathbf{x}}$ solve the normal equations,

The weights are the intercept and the slope. No calculus is needed: the right angle does the work.

Fitting the line

Here $\mathbf{A}^\top\mathbf{A}=\begin{bmatrix}3&3\\3&5\end{bmatrix}$: 3 points, the $t$ values add to 3, their squares add to 5. And $\mathbf{A}^\top\mathbf{y}=(6,7)$: the heights add to 6, and $0\cdot1+1\cdot3+2\cdot2=7$. So

which gives $c_1=0.5$ and $c_0=1.5$. The line is $y=1.5+0.5t$. Its heights are $\mathbf{p}=(1.5,2,2.5)$ and the misses are $\mathbf{e}=\mathbf{y}-\mathbf{p}=(-0.5,1,-0.5)$.

Here $\mathbf{e}$ is the list of misses, called the residuals. Signal processing writes an error signal $e[n]$; this bold $\mathbf{e}$ is the same idea as a vector.

After the clip, drag the middle point up by 1. The slope stays $0.5$ and the intercept rises to $11/6=1.833$. The middle point sits at the mean of the $t$ values, so raising it lifts the line without tilting it.

The residuals

The residuals are at a right angle to every column, $\mathbf{A}^\top\mathbf{e}=\mathbf{0}$. The first column is all ones, so the residuals add up to zero: $-0.5+1-0.5=0$. The second column is $\mathbf{t}=(0,1,2)$, and $\mathbf{t}\cdot\mathbf{e}=0+1-1=0$. Any fit with a constant term has residuals that add up to zero.

The right angle also splits the lengths: $\lVert\mathbf{y}\rVert^2=14=12.5+1.5$. The fitted heights carry 12.5 and the residuals 1.5, the smallest sum of squared misses any line can reach.

The normal equations have exactly one answer when the columns of $\mathbf{A}$ point in different directions. If every $t$ were the same, the two columns would lie on one line, $\mathbf{A}^\top\mathbf{A}$ would have no inverse, and the slope would be undefined: through points stacked on one vertical line, no line can pick a slope.

A parabola: add a column

The method does not care what the columns are. To fit a parabola $c_0+c_1t+c_2t^2$, add a column of $t^2$. Take four points, $t=(-1,0,1,2)$ and $\mathbf{y}=(2,1,2,6)$, and compare a line with a parabola.

For the line, the normal equations are $\begin{bmatrix}4&2\\2&6\end{bmatrix}\hat{\mathbf{x}}=(11,12)$, so $\hat{\mathbf{x}}=(2.1,1.3)$. The residuals are $(1.2,-1.1,-1.4,1.3)$: they add up to 0, and their squares add up to $6.30$. As before, $\lVert\mathbf{y}\rVert^2=45=38.7+6.3$.

For the parabola, the normal equations are

The residuals are $(-0.05,0.15,-0.15,0.05)$, and their squares add up to only $0.05$. The extra column gave the fit room to bend.

More columns are not always better. With three points and three unknowns, the parabola $1+3.5t-1.5t^2$ passes through $(0,1)$, $(1,3)$ and $(2,2)$ exactly: zero error. But a curve that bends to hit every point also follows every bit of noise in them.

Worked example

1. A line through three points. $(0,1)$, $(1,3)$, $(2,2)$: $\mathbf{A}^\top\mathbf{A}=\begin{bmatrix}3&3\\3&5\end{bmatrix}$, $\mathbf{A}^\top\mathbf{y}=(6,7)$, so $y=1.5+0.5t$.
2. Residuals. $(-0.5,1,-0.5)$; they add up to 0; their squares add up to 1.5.
3. A check from statistics. The slope is also $\sum(t-\bar t)(y-\bar y)\big/\sum(t-\bar t)^2=1/2$, and the intercept is $\bar y-0.5\,\bar t=2-0.5=1.5$.
4. Two points. A line through two points has error 0: two equations, two unknowns.
5. Four points, line and parabola. Errors 6.30 and 0.05.
6. Predict. Raise the middle of the three points by 1: slope $0.5$, intercept $1.833$.

Where you’ll meet this

A sensor is calibrated by feeding it known inputs and fitting a line to its raw readings; the slope is its gain and the intercept its offset. A satellite navigation receiver solves for four unknowns, its position in three directions and its clock error, from every satellite it can hear, often eight or more equations, by repeated least squares. The trend line a spreadsheet draws through a chart is this fit.

The normal equations can lose accuracy when the columns are nearly parallel. QR factorisation solves the same problem a safer way.

Reference card