Projection Matrices and Least Squares

What the projection matrix does: two extreme cases

Last lecture ended with a magic formula — the projection matrix

$$P = A(A^TA)^{-1}A^T.$$

What is it doing? Multiply by any $\mathbf{b}$: $P\mathbf{b}$ is supposed to project $\mathbf{b}$ to the nearest point in the column space of $A$. Strang recaps by testing the two extreme cases.

Case 1: $\mathbf{b}$ is in the column space already. Then projecting should change nothing — $P\mathbf{b} = \mathbf{b}$. Why does the formula deliver that? A vector in the column space is a combination of the columns, and Strang insists you know how to write one: it has the form $A\mathbf{x}$. (“I’m going to stick that on the quiz or the final for sure.”) Feed $\mathbf{b} = A\mathbf{x}$ into the formula:

$$P\mathbf{b} = A(A^TA)^{-1}A^T A\mathbf{x} = A\underbrace{(A^TA)^{-1}(A^TA)}_{I}\,\mathbf{x} = A\mathbf{x} = \mathbf{b}.$$

Cancel, cancel — the $A^TA$ meets its inverse, leaving $A\mathbf{x}$, which was $\mathbf{b}$.

Case 2: $\mathbf{b}$ is perpendicular to the column space. Picture the column space as a plane and $\mathbf{b}$ sticking straight up at ninety degrees. The nearest point in the plane is the origin: $P\mathbf{b}$ should be $\mathbf{0}$. Which vectors are perpendicular to the column space? The four fundamental subspaces answer instantly: they are the vectors in the null space of $A^T$. So $A^T\mathbf{b} = \mathbf{0}$, and the formula dies right at its last factor:

$$P\mathbf{b} = A(A^TA)^{-1}\underbrace{A^T\mathbf{b}}_{\mathbf{0}} = \mathbf{0}.$$

The average vector is neither extreme: it has a piece $\mathbf{p}$ in the column space and a piece $\mathbf{e}$ perpendicular to it. The projection preserves the first piece and kills the second, and the two pieces add back to the original: $\mathbf{p} + \mathbf{e} = \mathbf{b}$.

The best straight line through three points

Now put the formula to work on the problem started at the end of last lecture. Three data points: at times $t = 1, 2, 3$ the measured heights are $b = 1, 2, 2$. The first two points suggest a nice forty-five-degree line — but the third point doesn’t lie on it. No line goes through all three. We want the best line $y = C + Dt$.

If a line did go through all three points, $C$ and $D$ would solve three equations:

$$\begin{aligned} C + D &= 1 \\ C + 2D &= 2 \\ C + 3D &= 2 \end{aligned} \qquad\text{i.e.}\qquad \underbrace{\begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}}_{A} \begin{bmatrix} C \\ D \end{bmatrix} = \underbrace{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}}_{\mathbf{b}}$$

Three equations, two unknowns, no solution: the two columns of $A$ are independent — they’re a basis for the column space — but that column space doesn’t contain $\mathbf{b}$.

Strang keeps two pictures on the board, and insists you see both. Picture one is in the $t$–$y$ plane: three points, a candidate line, and three vertical errors $e_1, e_2, e_3$ — the gap at each $t$ between the data value $b_i$ and the line’s value $p_i$. Picture two is a vector picture in $\mathbb{R}^3$: the vector $\mathbf{b} = (1,2,2)$, the column space of $A$ spanned by $(1,1,1)$ and $(1,2,3)$, and the nearest point $\mathbf{p} = (p_1, p_2, p_3)$ in that column space. Same problem twice: if we replaced the data $1, 2, 2$ by the numbers $p_1, p_2, p_3$, the three equations would be solvable — a line goes through the $p$‘s — because the vector $\mathbf{p}$ is in the column space. It’s the closest such vector.

An aside Strang takes seriously: fitting straight lines is a big part of statistics — the right word is regression, linear regression, and this sum of squares is its measure of error. Statisticians like it because it leads to a beautiful linear system, but they’re careful about the squaring. Suppose a fourth measurement at $t = 0$ was way off. Its squared error would be way out of sight compared to the others, and the whole problem turns topsy-turvy over one point — an outlier, which could be a mistake after all. Least squares is the most used method, but not exclusively used, because it overcompensates for outliers.

Solving the normal equations

How to find $\hat{\mathbf{x}} = (\hat{C}, \hat{D})$?

Compute the pieces:

$$A^TA = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix} = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}, \qquad A^T\mathbf{b} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} = \begin{bmatrix} 5 \\ 11 \end{bmatrix}$$

And what do we expect of $A^TA$ before continuing? Symmetric — check. Invertible — check. (Near the end of the course Strang will add: positive definite, a future fact about this crucial matrix.) The normal equations, written out:

$$\begin{aligned} 3C + 6D &= 5 \\ 6C + 14D &= 11 \end{aligned}$$

Before solving, Strang derives the same equations a second way — from calculus. The total squared error is a function of two variables,

$$E(C, D) = (C + D - 1)^2 + (C + 2D - 2)^2 + (C + 3D - 2)^2,$$

and at the minimum both partial derivatives vanish. Because we’re differentiating squares, the derivatives are linear — that’s the beauty of these squares — and $\partial E/\partial C = 0$ gives the first normal equation, $\partial E/\partial D = 0$ the second. Wherever you look, these equations keep coming.

Now solve by elimination, “because that’s the only thing I know how to do”: subtract twice the first equation from the second to get $2D = 1$, so $D = \tfrac{1}{2}$; back substitution gives $3C + 3 = 5$, so $C = \tfrac{2}{3}$. The best line is

$$y = \tfrac{2}{3} + \tfrac{1}{2}t.$$

The projection p and the error e

With the line in hand, read off the points on the line — the components of $\mathbf{p}$:

What do we know about this error vector? First, $\mathbf{p} + \mathbf{e} = \mathbf{b}$ — the two pieces rebuild the original. Second, $\mathbf{p}$ and $\mathbf{e}$ are perpendicular. Dare to verify: the dot product is $-\tfrac{7}{36} + \tfrac{20}{36} - \tfrac{13}{36} = 0$. (“Thank you, God.”)

But we know even a little more: $\mathbf{e}$ is perpendicular not just to this particular $\mathbf{p}$ — it’s perpendicular to the whole column space. Test it against a nice vector in the column space, $(1,1,1)$: the dot product is $-\tfrac{1}{6} + \tfrac{2}{6} - \tfrac{1}{6} = 0$. And against $(1,2,3)$: $-\tfrac{1}{6} + \tfrac{4}{6} - \tfrac{3}{6} = 0$ again.

Why A transpose A is invertible

The whole calculation leaned on $A^TA$ being invertible — Strang announced it as the chapter started, and now he pays the debt with a proof. He doesn’t hammer away at many proofs in this course, “but this is like the central fact and it brings in all the stuff we know.”

(If $A$ has independent columns and $A\mathbf{x} = \mathbf{0}$, then $\mathbf{x} = \mathbf{0}$ — Strang flags that implication too as “a fill-in question on the final exam.”)

Looking ahead: orthonormal columns

One case makes the geometry even better. Columns are certainly independent if they’re perpendicular — ruling out the zero column by giving them all length one. Perpendicular unit vectors, like $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, are called orthonormal: ortho for perpendicular, normal for unit length. Those are the best columns you could ask for — for the matrix with those three columns, $A^TA$ is the identity.

A final example, Strang’s absolute favorite pair of orthonormal vectors in the plane:

$$\begin{bmatrix} \cos\theta \\ \sin\theta \end{bmatrix}, \qquad \begin{bmatrix} -\sin\theta \\ \cos\theta \end{bmatrix}$$

Both unit vectors, and the angle between them is ninety degrees. The job next time: see why orthonormal vectors are great, and then make vectors orthonormal by picking the right basis.

Problems

Work these before revealing the solutions — the lecture’s worked example is the template for all of them.

Problem 16.1 Best line through three points

Find the best straight line $y = C + Dt$ through the points $(1, 0)$, $(2, 1)$, $(3, 3)$ in the least squares sense. Set up $A$, $\mathbf{b}$, and the normal equations, then solve for $\hat{C}$ and $\hat{D}$.

Show solution

The three (unsolvable) equations are $C + D = 0$, $C + 2D = 1$, $C + 3D = 3$, so

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

Then $A^TA = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}$ (same matrix as the lecture — same $t$‘s) and $A^T\mathbf{b} = \begin{bmatrix} 0 + 1 + 3 \\ 0 + 2 + 9 \end{bmatrix} = \begin{bmatrix} 4 \\ 11 \end{bmatrix}$.

Normal equations: $3C + 6D = 4$ and $6C + 14D = 11$. Subtract twice the first from the second: $2D = 3$, so $D = \tfrac{3}{2}$. Back substitute: $3C + 9 = 4$, so $C = -\tfrac{5}{3}$. Best line: $y = -\tfrac{5}{3} + \tfrac{3}{2}t$.

Problem 16.2 Check p + e = b and orthogonality

For the line found in Problem 16.1, compute the projection $\mathbf{p} = A\hat{\mathbf{x}}$ and the error $\mathbf{e} = \mathbf{b} - \mathbf{p}$. Verify that $\mathbf{e}$ is perpendicular to both columns of $A$.

Show solution

Evaluate the line at $t = 1, 2, 3$: $-\tfrac{5}{3} + \tfrac{3}{2} = -\tfrac{1}{6}$, then $-\tfrac{5}{3} + 3 = \tfrac{4}{3}$, then $-\tfrac{5}{3} + \tfrac{9}{2} = \tfrac{17}{6}$. So

$$\mathbf{p} = \begin{bmatrix} -1/6 \\ 4/3 \\ 17/6 \end{bmatrix}, \qquad \mathbf{e} = \mathbf{b} - \mathbf{p} = \begin{bmatrix} 1/6 \\ -1/3 \\ 1/6 \end{bmatrix}.$$

Against $(1,1,1)$: $\tfrac{1}{6} - \tfrac{2}{6} + \tfrac{1}{6} = 0$. Against $(1,2,3)$: $\tfrac{1}{6} - \tfrac{4}{6} + \tfrac{3}{6} = 0$. Both zero, so $\mathbf{e}$ is perpendicular to the whole column space — the same $(\tfrac{1}{6}, -\tfrac{2}{6}, \tfrac{1}{6})$ pattern of errors as the lecture, with signs flipped.

Problem 16.3 Extreme cases of P

Let $A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$ as in the lecture. Without computing $P$ entry by entry, find $P\mathbf{b}$ for (a) $\mathbf{b} = \begin{bmatrix} 2 \\ 3 \\ 4 \end{bmatrix}$ and (b) $\mathbf{b} = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix}$. Justify each answer using the two extreme cases.

Show solution

(a) $\mathbf{b} = (2,3,4)$ is in the column space: it equals $1\cdot(1,1,1) + 1\cdot(1,2,3)$, i.e. $\mathbf{b} = A\mathbf{x}$ with $\mathbf{x} = (1,1)$. Vectors already in the column space are unchanged by projection, so $P\mathbf{b} = \mathbf{b} = (2,3,4)$.

(b) Check $\mathbf{b} = (1,-2,1)$ against the columns: $(1,-2,1)\cdot(1,1,1) = 0$ and $(1,-2,1)\cdot(1,2,3) = 1 - 4 + 3 = 0$. So $A^T\mathbf{b} = \mathbf{0}$: this $\mathbf{b}$ is in the null space of $A^T$, perpendicular to the column space, and the formula kills it at its last factor. $P\mathbf{b} = \mathbf{0}$.

Problem 16.4 I minus P is a projection

Suppose $P$ is a projection matrix, so $P^T = P$ and $P^2 = P$. Show algebraically that $Q = I - P$ satisfies the same two properties, and identify the subspace that $Q$ projects onto when $P$ projects onto the column space of $A$.

Show solution

Symmetric: $Q^T = (I - P)^T = I^T - P^T = I - P = Q$.

Idempotent: $Q^2 = (I - P)(I - P) = I - P - P + P^2 = I - 2P + P = I - P = Q$, using $P^2 = P$.

$Q\mathbf{b} = \mathbf{b} - P\mathbf{b} = \mathbf{e}$, the error part of $\mathbf{b}$. Since $\mathbf{e}$ is perpendicular to the column space, $Q$ projects onto the orthogonal complement of $C(A)$ — the null space of $A^T$.

Problem 16.5 When A transpose A fails

Let $A = \begin{bmatrix} 1 & 2 \\ 1 & 2 \\ 1 & 2 \end{bmatrix}$, whose columns are dependent. Compute $A^TA$ and show directly that it is singular, by finding a nonzero vector in its null space. Explain how this fits the theorem proved in lecture.

Show solution

$$A^TA = \begin{bmatrix} 1 & 1 & 1 \\ 2 & 2 & 2 \end{bmatrix} \begin{bmatrix} 1 & 2 \\ 1 & 2 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 3 & 6 \\ 6 & 12 \end{bmatrix}.$$

The second row is twice the first, so $A^TA$ is singular. Take $\mathbf{x} = \begin{bmatrix} 2 \\ -1 \end{bmatrix}$: then $A^TA\mathbf{x} = \begin{bmatrix} 6 - 6 \\ 12 - 12 \end{bmatrix} = \mathbf{0}$.

This is exactly the lecture’s theorem run in reverse: the proof showed $A^TA\mathbf{x} = \mathbf{0}$ forces $A\mathbf{x} = \mathbf{0}$, and indeed $A\mathbf{x} = 2\mathbf{c}_1 - \mathbf{c}_2 = \mathbf{0}$ here because column two is twice column one. Dependent columns give $A$ a nonzero null space, and $A^TA$ inherits it — the theorem’s hypothesis of independent columns is necessary, not just convenient.