Least Squares and the Line of Best Fit

Quick answer

An inconsistent system Ax = b has no exact solution, but it has a best approximate one. A least-squares solution x̂ makes Ax̂ the point of the column space closest to b, which is the orthogonal projection of b onto Col A. The error b − Ax̂ is then orthogonal to every column of A, which is the statement Aᵀ(b − Ax̂) = 0, or the normal equations AᵀAx̂ = Aᵀb. Fitting a line y = β₀ + β₁x to data points is the most common case, and it minimizes the sum of the squared vertical errors.

What you'll learn

Explain a least-squares solution geometrically
Set up and solve the normal equations
Fit a line of best fit to data with a design matrix
Check a fit through its residuals

When there is no solution

Four measurements, one line: the points $(1, 1)$ , $(2, 3)$ , $(3, 4)$ and $(4, 4)$ do not lie on any line $y = \beta_0 + \beta_1x$ . Demanding that they did gives four equations in two unknowns,

\begin{bmatrix} 1 & 1\\ 1 & 2\\ 1 & 3\\ 1 & 4 \end{bmatrix} \begin{bmatrix} \beta_0 \\ \beta_1 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 4 \\ 4 \end{bmatrix}

and the system is inconsistent. The useful question is not whether it has a solution but which $\boldsymbol{\beta}$ comes closest.

A least-squares solution of $A\mathbf{x} = \mathbf{b}$ is a vector $\hat{\mathbf{x}}$ with $\|\mathbf{b} - A\hat{\mathbf{x}}\| \le \|\mathbf{b} - A\mathbf{x}\|$ for every $\mathbf{x}$ .

The name comes from the quantity minimized: $\|\mathbf{b} - A\mathbf{x}\|^2$ is the sum of the squares of the individual errors.

Why the normal equations find it

As $\mathbf{x}$ varies, $A\mathbf{x}$ runs over the column space of $A$ . The point of $\text{Col}\,A$ closest to $\mathbf{b}$ is its orthogonal projection $\hat{\mathbf{b}}$ , and the error $\mathbf{b} - \hat{\mathbf{b}}$ is orthogonal to $\text{Col}\,A$ . So $\hat{\mathbf{x}}$ is exactly a solution of $A\mathbf{x} = \hat{\mathbf{b}}$ , and the error must be orthogonal to every column $\mathbf{a}_j$ :

\mathbf{a}_j \cdot (\mathbf{b} - A\hat{\mathbf{x}}) = 0 \quad\text{for every } j

The transpose $A^{\mathsf{T}}$ has the columns of $A$ as its rows, so $A^{\mathsf{T}}\mathbf{v}$ lists the dot products of the columns with $\mathbf{v}$ . All the orthogonality conditions together read $A^{\mathsf{T}}(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$ , which rearranges to the normal equations:

A^{\mathsf{T}}A\,\hat{\mathbf{x}} = A^{\mathsf{T}}\mathbf{b}

The best approximation leaves an error perpendicular to the column space, and the normal equations are that perpendicularity written column by column. When the columns of $A$ are independent, $A^{\mathsf{T}}A$ is invertible and the solution is unique.

Example 1 — An inconsistent system

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

The system asks for $x_1 = 1$ , $x_2 = 1$ and $x_1 + x_2 = 0$ at once, which is impossible. The normal equations are

A^{\mathsf{T}}A = \begin{bmatrix} 2 & 1\\ 1 & 2 \end{bmatrix} \qquad A^{\mathsf{T}}\mathbf{b} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \qquad \hat{\mathbf{x}} = \begin{bmatrix} \tfrac{1}{3} \\ \tfrac{1}{3} \end{bmatrix}

The error is $\mathbf{b} - A\hat{\mathbf{x}} = \left(\tfrac{2}{3}, \tfrac{2}{3}, -\tfrac{2}{3}\right)$ , and its dot products with the two columns are $\tfrac{2}{3} - \tfrac{2}{3} = 0$ and $\tfrac{2}{3} - \tfrac{2}{3} = 0$ , as the theory requires.

The line of best fit

For data $(x_1, y_1), \ldots, (x_n, y_n)$ and a line $y = \beta_0 + \beta_1x$ , build the design matrix $X$ from a column of $1$ s and the column of $x$ -values, and solve

X^{\mathsf{T}}X\,\boldsymbol{\beta} = X^{\mathsf{T}}\mathbf{y}

The errors being squared are the vertical distances from the points to the line, called residuals.

Worked examples

Common mistakes

Practice problems

Find the transpose of $\begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6 \end{bmatrix}$ .

Answer

$\begin{bmatrix} 1 & 4\\ 2 & 5\\ 3 & 6 \end{bmatrix}$

Full solution

The rows become the columns.
For the points $(1, 1)$ , $(2, 2)$ and $(3, 2)$ , write the design matrix and compute $X^{\mathsf{T}}X$ and $X^{\mathsf{T}}\mathbf{y}$ .

Answer

$X^{\mathsf{T}}X = \begin{bmatrix} 3 & 6\\ 6 & 14 \end{bmatrix}$ and $X^{\mathsf{T}}\mathbf{y} = (5, 11)$

Full solution

$X$ has rows $(1, 1)$ , $(1, 2)$ and $(1, 3)$ . The entries of $X^{\mathsf{T}}X$ are $3$ points, $1 + 2 + 3 = 6$ , and $1 + 4 + 9 = 14$ . And $X^{\mathsf{T}}\mathbf{y} = (1 + 2 + 2,\ 1 + 4 + 6)$ .
Solve the normal equations from exercise 2 for the best line.

Answer

$y = \tfrac{2}{3} + \tfrac{1}{2}x$

Full solution

$3\beta_0 + 6\beta_1 = 5$ and $6\beta_0 + 14\beta_1 = 11$ . Doubling the first and subtracting gives $2\beta_1 = 1$ , so $\beta_1 = \tfrac{1}{2}$ and $\beta_0 = \tfrac{5 - 3}{3} = \tfrac{2}{3}$ .
Find the least-squares line for $(-1, 0)$ , $(0, 1)$ and $(1, 3)$ .

Answer

$y = \tfrac{4}{3} + 1.5x$

Full solution

$X^{\mathsf{T}}X = \begin{bmatrix} 3 & 0\\ 0 & 2 \end{bmatrix}$ because the $x$ -values add to $0$ , and $X^{\mathsf{T}}\mathbf{y} = (4, 3)$ . So $\beta_0 = \tfrac{4}{3}$ and $\beta_1 = \tfrac{3}{2}$ .
Find the residuals of the fit in exercise 4, and check that they add to zero.

Answer

$\tfrac{1}{6}$ , $-\tfrac{1}{3}$ and $\tfrac{1}{6}$

Full solution

The line gives $-\tfrac{1}{6}$ , $\tfrac{4}{3}$ and $\tfrac{17}{6}$ at the three $x$ -values. Subtracting from $0$ , $1$ , $3$ gives the residuals, and $\tfrac{1}{6} - \tfrac{2}{6} + \tfrac{1}{6} = 0$ .
Find the least-squares solution of $\begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix}\mathbf{x} = \begin{bmatrix} 3 \\ 1 \end{bmatrix}$ .

Answer

$(2, 1)$ , the exact solution

Full solution

The system is consistent, so the smallest possible error, zero, is reached at its solution. The normal equations $\begin{bmatrix} 2 & 0\\ 0 & 2 \end{bmatrix}\hat{\mathbf{x}} = \begin{bmatrix} 4 \\ 2 \end{bmatrix}$ agree.
When does $A\mathbf{x} = \mathbf{b}$ have exactly one least-squares solution?

Answer

When the columns of $A$ are linearly independent

Full solution

Then $A^{\mathsf{T}}A$ is invertible and $\hat{\mathbf{x}} = (A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}\mathbf{b}$ . With dependent columns, many $\mathbf{x}$ give the same projection $A\hat{\mathbf{x}}$ .
What is $A\hat{\mathbf{x}}$ , geometrically?

Answer

The orthogonal projection of $\mathbf{b}$ onto $\text{Col}\,A$

Full solution

$A\hat{\mathbf{x}}$ is the point of the column space closest to $\mathbf{b}$ , and the closest point of a subspace is the orthogonal projection.
If $\mathbf{b}$ is orthogonal to every column of $A$ , and the columns are independent, what is $\hat{\mathbf{x}}$ ?

Answer

$\hat{\mathbf{x}} = \mathbf{0}$

Full solution

Then $A^{\mathsf{T}}\mathbf{b} = \mathbf{0}$ , and the normal equations $A^{\mathsf{T}}A\hat{\mathbf{x}} = \mathbf{0}$ with invertible $A^{\mathsf{T}}A$ force $\hat{\mathbf{x}} = \mathbf{0}$ . The projection of $\mathbf{b}$ onto the column space is the origin.
A student fits a line to four points by picking two of them and drawing the line through those. What went wrong?

Hint

What happens to the other two points?

Answer

The line ignores half the data. Least squares uses all four points and minimizes the total squared error.

Full solution

The line through $(2, 3)$ and $(4, 4)$ , for instance, is $y = 2 + 0.5x$ , with residuals $-1.5$ , $0$ , $0.5$ and $0$ and squared error $2.5$ , worse than the $1$ achieved by $y = 0.5 + x$ . Only the normal equations balance every point at once.

Frequently asked questions

What is a least-squares solution?

A vector x̂ that makes ‖b − Ax̂‖ as small as possible. When Ax = b is consistent it is an ordinary solution; otherwise it is the best approximation.

What are the normal equations?

AᵀAx̂ = Aᵀb. They say the error b − Ax̂ is orthogonal to every column of A.

Why is it called least squares?

It minimizes ‖b − Ax‖², which is the sum of the squares of the individual errors.

When is the least-squares solution unique?

When the columns of A are linearly independent. Then AᵀA is invertible and x̂ = (AᵀA)⁻¹Aᵀb.

How do you fit a line to data with matrices?

Put a column of 1s and the column of x-values into a design matrix X, the y-values into a vector y, and solve XᵀXβ = Xᵀy for the intercept and slope.

For teachersPrint problems onlyTick to print a blank worksheet; leave it clear to print the lesson with the full answer key.