Math Core

Real data rarely fits a model exactly. Measure four points that "should" lie on a line and they won't quite; the system $A\mathbf{x} = \mathbf{b}$ for the line's coefficients has no solution. Instead of giving up, you ask for the $\mathbf{x}$ that makes $A\mathbf{x}$ as close to $\mathbf{b}$ as possible. Orthogonal projection answers that question exactly.

The least-squares problem

Definition

Least-squares solution

If $A$ is $m \times n$ and $\mathbf{b}$ is in $\mathbb{R}^m$ , a least-squares solution of $A\mathbf{x} = \mathbf{b}$ is a vector $\hat{\mathbf{x}}$ in $\mathbb{R}^n$ such that

\|\mathbf{b} - A\hat{\mathbf{x}}\| \le \|\mathbf{b} - A\mathbf{x}\| \quad \text{for all } \mathbf{x} \text{ in } \mathbb{R}^n.

The name comes from the fact that $\|\mathbf{b} - A\mathbf{x}\|^2$ is a sum of squares of the entries of $\mathbf{b} - A\mathbf{x}$ . The number $\|\mathbf{b} - A\hat{\mathbf{x}}\|$ is the least-squares error.

The vectors $A\mathbf{x}$ are exactly the vectors in $\operatorname{Col} A$ . So you want the point of $\operatorname{Col} A$ closest to $\mathbf{b}$ , and by the best approximation theorem that is

\hat{\mathbf{b}} = \operatorname{proj}_{\operatorname{Col} A}\mathbf{b}.

Since $\hat{\mathbf{b}}$ is in $\operatorname{Col} A$ , the equation $A\mathbf{x} = \hat{\mathbf{b}}$ is consistent, and its solutions are the least-squares solutions.

The normal equations

You usually don't have an orthogonal basis for $\operatorname{Col} A$ , so computing $\hat{\mathbf{b}}$ directly is awkward. Instead, use the key property of the projection: $\mathbf{b} - A\hat{\mathbf{x}}$ is orthogonal to $\operatorname{Col} A$ , so it is orthogonal to every column of $A$ . That means $A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$ , or:

The normal equations

The least-squares solutions of $A\mathbf{x} = \mathbf{b}$ are exactly the solutions of

A^TA\mathbf{x} = A^T\mathbf{b}.

This system is always consistent. If the columns of $A$ are linearly independent, then $A^TA$ is invertible and the least-squares solution is unique:

\hat{\mathbf{x}} = (A^TA)^{-1}A^T\mathbf{b}.

If the columns of $A$ are dependent, there are infinitely many least-squares solutions (they all give the same $A\hat{\mathbf{x}} = \hat{\mathbf{b}}$ ).

Worked example: Solving with the normal equations

Find the least-squares solution of $A\mathbf{x} = \mathbf{b}$ and the least-squares error, where

A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 2 \\ 1 \\ 6 \end{bmatrix}.

The system is inconsistent: rows 1 and 2 force $x_1 = 2$ , $x_2 = 1$ , but then row 3 gives $3 \neq 6$ . Compute

A^TA = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, \qquad A^T\mathbf{b} = \begin{bmatrix} 2 + 6 \\ 1 + 6 \end{bmatrix} = \begin{bmatrix} 8 \\ 7 \end{bmatrix}.

Solve $2x_1 + x_2 = 8$ , $x_1 + 2x_2 = 7$ : subtracting twice the second from the first gives $-3x_2 = -6$ , so $x_2 = 2$ and $x_1 = 3$ . Thus $\hat{\mathbf{x}} = (3, 2)$ .

Then $A\hat{\mathbf{x}} = (3, 2, 5)$ and $\mathbf{b} - A\hat{\mathbf{x}} = (-1, -1, 1)$ . Check it is orthogonal to both columns: $(-1, -1, 1) \cdot (1, 0, 1) = 0$ and $(-1, -1, 1) \cdot (0, 1, 1) = 0$ . The least-squares error is $\sqrt{1 + 1 + 1} = \sqrt{3}$ .

Common mistake

Don't "solve" $A\mathbf{x} = \mathbf{b}$ by cancelling $A^T$ from $A^TA\mathbf{x} = A^T\mathbf{b}$ , and don't write $\hat{\mathbf{x}} = A^{-1}\mathbf{b}$ : a non-square $A$ has no inverse. The whole point is that $A\mathbf{x} = \mathbf{b}$ has no solution, while the square system $A^TA\mathbf{x} = A^T\mathbf{b}$ does. Also remember that $\hat{\mathbf{x}}$ lives in $\mathbb{R}^n$ while $\hat{\mathbf{b}} = A\hat{\mathbf{x}}$ lives in $\mathbb{R}^m$ .

Fitting a line to data

Given data points $(x_1, y_1), \ldots, (x_m, y_m)$ , you want the line $y = \beta_0 + \beta_1x$ that fits best. Asking every point to lie on the line gives $m$ equations $\beta_0 + \beta_1x_i = y_i$ , that is, $X\boldsymbol{\beta} = \mathbf{y}$ with

X = \begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_m \end{bmatrix}, \qquad \boldsymbol{\beta} = \begin{bmatrix} \beta_0 \\ \beta_1 \end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{bmatrix}.

$X$ is the design matrix. The least-squares solution gives the least-squares line (the regression line), which minimizes the sum of the squared vertical distances from the points to the line. The normal equations are

X^TX = \begin{bmatrix} m & \sum x_i \\ \sum x_i & \sum x_i^2 \end{bmatrix}, \qquad X^T\mathbf{y} = \begin{bmatrix} \sum y_i \\ \sum x_iy_i \end{bmatrix}.

Worked example: The least-squares line

Find the least-squares line for the points $(0, 1)$ , $(1, 1)$ , $(2, 2)$ , $(3, 4)$ .

Here $m = 4$ , $\sum x_i = 6$ , $\sum x_i^2 = 0 + 1 + 4 + 9 = 14$ , $\sum y_i = 8$ and $\sum x_iy_i = 0 + 1 + 4 + 12 = 17$ . The normal equations are

\begin{aligned} 4\beta_0 + 6\beta_1 &= 8 \\ 6\beta_0 + 14\beta_1 &= 17. \end{aligned}

The determinant is $56 - 36 = 20$ , so by Cramer's rule

\beta_0 = \frac{8(14) - 6(17)}{20} = \frac{10}{20} = \frac{1}{2}, \qquad \beta_1 = \frac{4(17) - 6(8)}{20} = \frac{20}{20} = 1.

The least-squares line is $y = \tfrac{1}{2} + x$ . Its predictions $0.5, 1.5, 2.5, 3.5$ miss the data by $0.5, -0.5, -0.5, 0.5$ , and the sum of squared residuals is $4(0.25) = 1$ . No other line does better.

The least-squares line y = 1/2 + x for the points (0, 1), (1, 1), (2, 2), (3, 4). Each point is off by 1/2 vertically.Open in grapher →

The same method fits any model that is linear in its coefficients, such as a parabola $y = \beta_0 + \beta_1x + \beta_2x^2$ : the design matrix just gets a column of $x_i^2$ .

Shortcuts: orthogonal columns and QR

If the columns $\mathbf{a}_1, \ldots, \mathbf{a}_n$ of $A$ are orthogonal, $A^TA$ is diagonal, and each entry of $\hat{\mathbf{x}}$ is a weight from the projection formula:

\hat{x}_j = \frac{\mathbf{b} \cdot \mathbf{a}_j}{\mathbf{a}_j \cdot \mathbf{a}_j}.

More generally, if $A = QR$ , then $A^TA = R^TR$ and $A^T\mathbf{b} = R^TQ^T\mathbf{b}$ , and the normal equations reduce to the triangular system

R\hat{\mathbf{x}} = Q^T\mathbf{b},

solved by back substitution. This is how software computes least-squares solutions: forming $A^TA$ explicitly can magnify rounding errors.

Worked example: Orthogonal columns

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

The columns $\mathbf{a}_1 = (1, 1, 1)$ and $\mathbf{a}_2 = (-1, 1, 0)$ are orthogonal: $-1 + 1 + 0 = 0$ . So

\hat{x}_1 = \frac{2 + 6 + 1}{3} = 3, \qquad \hat{x}_2 = \frac{-2 + 6 + 0}{2} = 2, \qquad \hat{\mathbf{x}} = (3, 2).

Check: $\mathbf{b} - A\hat{\mathbf{x}} = (2, 6, 1) - (1, 5, 3) = (1, 1, -2)$ , which is orthogonal to both columns.

Tip

After solving, compute the residual $\mathbf{b} - A\hat{\mathbf{x}}$ and dot it with each column of $A$ . Every result must be $0$ . For a fitted line with an intercept, this says the residuals add up to $0$ .

Practice

Practice 1

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

Enter a point like (2, -3)

Practice 2

For the system in the previous problem, find the least-squares error $\|\mathbf{b} - A\hat{\mathbf{x}}\|$ as an exact value.

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 3

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

Enter a point like (2, -3)

Practice 4

Find the slope of the least-squares line $y = \beta_0 + \beta_1x$ for the points $(1, 2)$ , $(2, 3)$ , $(3, 5)$ .

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

Find the least-squares line for the points $(-1, 0)$ , $(0, 1)$ , $(1, 3)$ , and use it to predict $y$ when $x = 2$ .

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

The columns of $A = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \\ 1 & -1 \end{bmatrix}$ are orthogonal. Find the least-squares solution of $A\mathbf{x} = \mathbf{b}$ for $\mathbf{b} = (4, 0, 2, 2)$ .

Enter a point like (2, -3)

Practice 7

Let $\hat{\mathbf{x}}$ be a least-squares solution of $A\mathbf{x} = \mathbf{b}$ . Which statement is always true?