Least Squares and Orthogonal Projection, linear algebra I lesson

Three measurements give the points $(0, 1)$ , $(1, 2)$ and $(2, 2)$ . The line through the first two points predicts $3$ at input $2$ , and the horizontal line through the last two misses the first point, so no straight line passes through all three. The linear system for an intercept and a slope that match all three outputs has no solution, yet some lines clearly fit better than others. This lesson fixes what “best” means, the smallest sum of squared errors, and shows that orthogonal projection both finds the best fit and proves that nothing does better.

Key terms

Vertical residuals

Definition Suppose the data points $(t_1, y_1), \dots, (t_m, y_m)$ are compared with a line $y = a + bt$ with intercept $a$ and slope $b$ . The residual of observation $i$ is

r_i = y_i - (a + bt_i),

the measured output minus the predicted output at the same input $t_i$ . In the plot it is the signed vertical distance from the line to the point, positive when the point lies above the line and negative when it lies below. The inputs $t_i$ are treated as exact and are never moved.

In plain words A residual says how far the line misses one measurement, measured straight up or down at that measurement’s input. Its size is never smaller than the shortest distance from the point to the line, and it is larger whenever the line is sloped and misses the point.

Example For the three points above, the line $y = 1 + t$ predicts $1$ , $2$ and $3$ , so its residuals are $0$ , $0$ and $-1$ . The horizontal line $y = 2$ has residuals $-1$ , $0$ and $0$ . At the point $(2, 2)$ the vertical residual of $y = 1 + t$ has size $1$ , while the perpendicular distance from that point to the line is only $1/\sqrt{2}$ . Least squares works with the vertical residual.

Sum of squared errors

Definition For a line with coefficients $a$ and $b$ , the sum of squared errors is

S(a, b) = \sum_{i=1}^{m} \bigl(y_i - a - bt_i\bigr)^2 .

Least squares uses this number as its error criterion, with every observation weighted equally. Squaring keeps positive and negative residuals from canceling, and it counts large misses more heavily than small ones. If the outputs carry a unit, the sum carries the square of that unit.

In plain words Square each miss and add. A smaller total means a closer fit in this particular sense. It is a chosen criterion, and a problem whose measurements deserve different trust may call for weights instead.

Example For the points $(0, 1)$ , $(1, 2)$ and $(2, 2)$ ,

\begin{aligned} S(a, b) &= (1 - a)^2 + (2 - a - b)^2 \\[0.4em] &\quad + (2 - a - 2b)^2 . \end{aligned}

The lines $y = 1 + t$ and $y = 2$ both score $S = 1$ . Equal scores do not make either line best, and the next cards find a line that does better.

Residual vector in observation space

Definition Collect the outputs in the observation vector $\mathbf{y} = (y_1, \dots, y_m)$ in $\mathbb{R}^m$ and the coefficients in $\mathbf{c} = (a, b)$ . On this page a tuple written for a vector stands for a column, while pairs such as $(0, 1)$ are points in the plot. The design matrix $X$ is the $m \times 2$ matrix whose $i$ th row is $\begin{bmatrix} 1 & t_i \end{bmatrix}$ , so $X\mathbf{c}$ is the vector of predictions $a + bt_i$ . The residual vector is

\mathbf{r} = \mathbf{y} - X\mathbf{c}.

Its $i$ th coordinate is the vertical residual of observation $i$ , and $S(a, b) = \lVert \mathbf{y} - X\mathbf{c} \rVert^2$ . The space $\mathbb{R}^m$ is called observation space because it has one coordinate axis for each observation. Every possible prediction vector lies in $\operatorname{Col} X$ , and the system $X\mathbf{c} = \mathbf{y}$ is consistent exactly when $\mathbf{y}$ lies in $\operatorname{Col} X$ .

In plain words The scatter plot has one point per observation. Observation space turns the whole data set into a single vector, and every choice of coefficients into a single prediction vector in a flat subspace. The residual vector is the arrow from the prediction to the data, and its squared length is the sum of squared errors.

Example For the three points,

\begin{gathered} X = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}, \\[0.4em] X\mathbf{c} = \begin{bmatrix} a \\ a + b \\ a + 2b \end{bmatrix}. \end{gathered}

The column space of $X$ is a plane through the origin in $\mathbb{R}^3$ . The vector $\mathbf{y}$ is not in it, since the first two coordinates force $a = 1$ and $b = 1$ , and then the third prediction is $3$ instead of $2$ .

Least-squares solution

Definition Let $A$ be a real $m \times n$ matrix and $\mathbf{b}$ a vector in $\mathbb{R}^m$ . A vector $\hat{\mathbf{x}}$ in $\mathbb{R}^n$ is a least-squares solution of $A\mathbf{x} = \mathbf{b}$ if

\lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert^2 \le \lVert \mathbf{b} - A\mathbf{x} \rVert^2

for every $\mathbf{x}$ in $\mathbb{R}^n$ . Let $\mathbf{p}$ be the orthogonal projection of $\mathbf{b}$ onto $\operatorname{Col} A$ . For every $\mathbf{x}$ the vector $\mathbf{b} - \mathbf{p}$ is orthogonal to $\operatorname{Col} A$ and the vector $\mathbf{p} - A\mathbf{x}$ lies in it, so the Pythagorean theorem gives

\begin{aligned} \lVert \mathbf{b} - A\mathbf{x} \rVert^2 &= \lVert \mathbf{b} - \mathbf{p} \rVert^2 \\[0.4em] &\quad + \lVert \mathbf{p} - A\mathbf{x} \rVert^2 . \end{aligned}

Hence $\hat{\mathbf{x}}$ is a least-squares solution exactly when $A\hat{\mathbf{x}} = \mathbf{p}$ . Least-squares solutions always exist, the smallest value of $\lVert \mathbf{b} - A\mathbf{x} \rVert^2$ is $\lVert \mathbf{b} - \mathbf{p} \rVert^2$ , and when $\mathbf{b}$ lies in $\operatorname{Col} A$ the least-squares solutions are exactly the ordinary solutions. In a fitting problem the matrix is the design matrix $X$ , the unknown is the coefficient vector $\mathbf{c}$ and the right side is the observation vector $\mathbf{y}$ .

In plain words When no coefficients reproduce the data, take the prediction vector closest to the data. The closest point of a subspace is the foot of the perpendicular, and any other prediction adds a second, perpendicular piece of error. This proves a global minimum without calculus and without trying values one by one. The right angle lives in observation space. In the scatter plot the fitted line need not meet its vertical residual segments at right angles.

Example For the three points, the coefficients $\hat{\mathbf{c}} = (7/6, 1/2)$ give the predictions and residual

X\hat{\mathbf{c}} = \begin{bmatrix} 7/6 \\ 5/3 \\ 13/6 \end{bmatrix}, \qquad \mathbf{r} = \begin{bmatrix} -1/6 \\ 1/3 \\ -1/6 \end{bmatrix}.

The residual is orthogonal to both columns of $X$ , since $-\tfrac16 + \tfrac13 - \tfrac16 = 0$ and $0 \cdot (-\tfrac16) + 1 \cdot \tfrac13 + 2 \cdot (-\tfrac16) = 0$ . So the predictions are the projection $\mathbf{p}$ , and $\hat{\mathbf{c}}$ is a least-squares solution. Its score is $\tfrac{1}{36} + \tfrac19 + \tfrac{1}{36} = \tfrac16$ , less than the score $1$ of either earlier line. The best line is $y = \tfrac76 + \tfrac12 t$ .

Normal equations

Definition For a real $m \times n$ matrix $X$ and a vector $\mathbf{y}$ in $\mathbb{R}^m$ , the normal equations are

X^{\top}X\mathbf{c} = X^{\top}\mathbf{y}.

A vector $\mathbf{c}$ in $\mathbb{R}^n$ is a least-squares solution of $X\mathbf{c} = \mathbf{y}$ if and only if it satisfies the normal equations. The reason is that the entries of $X^{\top}(\mathbf{y} - X\mathbf{c})$ are the dot products of the residual with the columns of $X$ . The equations say the residual is orthogonal to every column, hence to all of $\operatorname{Col} X$ , and by the projection property that happens exactly when $X\mathbf{c} = \mathbf{p}$ . The normal equations always have at least one solution, even when $X\mathbf{c} = \mathbf{y}$ has none. The word normal means perpendicular.

In plain words The best residual has zero dot product with every column of the model. If it had a nonzero dot product with some vector $\mathbf{w}$ in $\operatorname{Col} X$ , moving the prediction a little in the direction of $\mathbf{w}$ or of $-\mathbf{w}$ would shrink the error. Writing the dot products for an unknown $\mathbf{c}$ gives a square system with one equation per coefficient.

Example For the three points,

X^{\top}X = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, \qquad X^{\top}\mathbf{y} = \begin{bmatrix} 5 \\ 6 \end{bmatrix},

so the normal equations are $3a + 3b = 5$ and $3a + 5b = 6$ . The coefficients $a = 7/6$ and $b = 1/2$ satisfy both, since $\tfrac72 + \tfrac32 = 5$ and $\tfrac72 + \tfrac52 = 6$ . The first equation comes from the all-ones column and says that the residuals sum to zero. A model without a constant column need not have residuals that sum to zero.

Fitted vector

Definition For a real $m \times n$ design matrix $X$ and observation vector $\mathbf{y}$ , the fitted vector is the orthogonal projection $\mathbf{p}$ of $\mathbf{y}$ onto $\operatorname{Col} X$ . It equals $X\hat{\mathbf{c}}$ for every least-squares solution $\hat{\mathbf{c}}$ , and it is unique, because by the identity above any prediction with the smallest error is at distance $0$ from $\mathbf{p}$ . If $\hat{\mathbf{c}}$ is one least-squares solution, all of them are the vectors $\hat{\mathbf{c}} + \mathbf{h}$ with $\mathbf{h}$ in $\operatorname{Null} X$ . So the coefficients are unique if and only if the columns of $X$ are linearly independent.

In plain words The best prediction is always one definite vector. Whether exactly one set of coefficients produces it depends on whether the model has redundant columns.

Example For the three points the columns of $X$ are independent, so $\hat{\mathbf{c}} = (7/6, 1/2)$ is the only least-squares solution, and the fitted vector is $(7/6, 5/3, 13/6)$ . Now fit a constant $a$ to the two observations $2$ and $6$ . The design column is $(1, 1)$ , and orthogonality says the residuals $2 - a$ and $6 - a$ add to zero, so $a = 4$ . The fitted vector is $(4, 4)$ , the residual is $(-2, 2)$ and the smallest squared error is $8$ . If the design matrix contains the all-ones column twice, the prediction depends only on the sum of the two coefficients, and every pair with sum $4$ gives the same fitted vector $(4, 4)$ .

Check yourself

For the points $(0, 1)$ , $(1, 1)$ and $(2, 4)$ , find the residual vector and the sum of squared errors of the line $y = 1 + t$ .

Show the answer

The line predicts $1$ , $2$ and $3$ . Subtracting the predictions from the observations gives the residual vector $(0, -1, 1)$ , and the sum of squared errors is $0 + 1 + 1 = 2$ .

For the same points, someone claims the least-squares line is $y = \tfrac12 + \tfrac32 t$ . Check the claim without solving any equations, and find its sum of squared errors.

Show the answer

The predictions are $\tfrac12$ , $2$ and $\tfrac72$ , so the residual vector is $(\tfrac12, -1, \tfrac12)$ . Its dot product with the all-ones column is $\tfrac12 - 1 + \tfrac12 = 0$ , and with the input column $(0, 1, 2)$ it is $0 - 1 + 1 = 0$ . The residual is orthogonal to $\operatorname{Col} X$ , so the predictions are the projection of the data and the claim is correct. The sum of squared errors is $\tfrac14 + 1 + \tfrac14 = \tfrac32$ , smaller than the score $2$ from the first question, as it must be.

Fit the model $y = bt$ , a line through the origin, to the points $(1, 1)$ and $(2, 3)$ . Do the residuals sum to zero?

Show the answer

The design matrix is the single column $(1, 2)$ and the observation vector is $(1, 3)$ . The normal equation is $5b = 1 + 6 = 7$ , so $b = \tfrac75$ . The fitted vector is $(\tfrac75, \tfrac{14}{5})$ and the residual is $(-\tfrac25, \tfrac15)$ . It is orthogonal to the design column, since $-\tfrac25 + 2 \cdot \tfrac15 = 0$ , but its entries sum to $-\tfrac15$ , not zero. Residuals are guaranteed to sum to zero only when the all-ones vector lies in $\operatorname{Col} X$ , for example when the model has an intercept, and this model has none.

Least Squares and Orthogonal Projection

Key terms

Vertical residuals

Sum of squared errors

Residual vector in observation space

Least-squares solution

Normal equations

Fitted vector

Check yourself

How this lesson connects

Builds on

Used later in