Projections onto Subspaces

Projecting onto a line

“We’re almost ready to make this lecture immortal,” Strang says — and it is an important one. It’s about projections. Start in two dimensions with the simplest case: a vector $\mathbf{b}$, and a line through a vector $\mathbf{a}$ — a one-dimensional subspace. Which point on that line is closest to $\mathbf{b}$?

The whole point of the picture is where orthogonality comes in. The closest point — the projection $\mathbf{p}$ of $\mathbf{b}$ onto the line — is the point where the connecting segment meets the line at a right angle. The error $\mathbf{e} = \mathbf{b} - \mathbf{p}$, “how much I’m wrong by,” is perpendicular to $\mathbf{a}$. That’s the one fact we know, and it’s got to tell us everything. (You could do this triangle with trigonometry, angles $\theta$, sines and cosines — that leads to “lousy formulas compared to linear algebra.”)

Since $\mathbf{p}$ lies on the line, it’s some multiple of $\mathbf{a}$: write $\mathbf{p} = x\mathbf{a}$, and the problem is to find the number $x$. The perpendicularity condition is

$$\mathbf{a}^T(\mathbf{b} - x\mathbf{a}) = 0$$

That’s the central equation. Simplify: $x\,\mathbf{a}^T\mathbf{a} = \mathbf{a}^T\mathbf{b}$, and since $\mathbf{a}^T\mathbf{a}$ is just a number — the length of $\mathbf{a}$ squared — divide by it:

$$x = \frac{\mathbf{a}^T\mathbf{b}}{\mathbf{a}^T\mathbf{a}}, \qquad \mathbf{p} = \mathbf{a}\,\frac{\mathbf{a}^T\mathbf{b}}{\mathbf{a}^T\mathbf{a}}$$

Two sanity checks before moving on. Double $\mathbf{b}$, and the projection doubles too — an extra factor $2$ rides straight through the formula. But double $\mathbf{a}$ and nothing changes: the line through $2\mathbf{a}$ (or $-\mathbf{a}$) is the same line, and indeed the formula picks up a factor $4$ above and a factor $4$ below, which cancel. The projection depends on the subspace, not on which vector you used to describe it.

Feel the formula before moving on — drag $\mathbf{b}$ anywhere and watch $\mathbf{p}$ slide along the line while $\mathbf{e}$ stays stubbornly perpendicular:

The projection matrix

Now lift this into matrices. The projection is some matrix acting on $\mathbf{b}$: $\mathbf{p} = P\mathbf{b}$. Reading the formula with the parentheses moved,

$$P = \frac{\mathbf{a}\,\mathbf{a}^T}{\mathbf{a}^T\mathbf{a}}$$

Don’t cancel! Below is $\mathbf{a}^T\mathbf{a}$, a number. Above is $\mathbf{a}\,\mathbf{a}^T$, a column times a row — a full-scale $n \times n$ matrix. And it’s an interesting one.

What’s its column space? Multiply $P$ by any vector $\mathbf{b}$ and you land on the line through $\mathbf{a}$ — so the column space of $P$ is exactly that line, and the rank is one. It’s exactly the form we know for a rank-one matrix: column times row, with that column as the basis for the column space.

So there are three formulas to remember from the one-dimensional case: the number $x = \mathbf{a}^T\mathbf{b}/\mathbf{a}^T\mathbf{a}$, the projection $\mathbf{p} = x\mathbf{a}$, and the matrix $P = \mathbf{a}\mathbf{a}^T/\mathbf{a}^T\mathbf{a}$. The same three will reappear, slightly changed, in $n$ dimensions.

Why project? Because Ax = b may have no solution

Why do we want projections at all? Because this chapter deals with systems $A\mathbf{x} = \mathbf{b}$ that have no solution — typically too many equations, more equations than unknowns. That’s the real problem.

So what do you do? “I solve the closest problem that I can solve.” The vector $A\mathbf{x}$ is always in the column space of $A$ — that’s the constraint — but $\mathbf{b}$ probably is not. So replace $\mathbf{b}$ by the closest vector that is in the column space:

$$A\hat{\mathbf{x}} = \mathbf{p}, \qquad \mathbf{p} = \text{projection of } \mathbf{b} \text{ onto the column space of } A$$

The hat on $\hat{\mathbf{x}}$ is a reminder: this is not the $\mathbf{x}$ that doesn’t exist — it’s the best possible $\mathbf{x}$.

Projecting onto a subspace

Now the real problem, in three dimensions: a plane, and a vector $\mathbf{b}$ not in the plane. Project $\mathbf{b}$ down into the plane. To get a formula we need to describe the plane: give a basis, two vectors $\mathbf{a}_1$ and $\mathbf{a}_2$. They don’t have to be perpendicular, but they’d better be independent. And here’s the clean move — that plane is a column space: it’s the column space of the matrix $A$ whose columns are $\mathbf{a}_1$ and $\mathbf{a}_2$. Everything is cleaner in terms of a matrix. (And once we can do two columns, we can do $n$.)

The projection $\mathbf{p}$ is some combination of the basis vectors — rather than writing $\hat{x}_1\mathbf{a}_1 + \hat{x}_2\mathbf{a}_2$, write it as $\mathbf{p} = A\hat{\mathbf{x}}$. The problem: find the right combination of columns so that the error is perpendicular to the plane. The error $\mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}}$ must be perpendicular to everything in the plane, and the plane is told to us by $\mathbf{a}_1$ and $\mathbf{a}_2$, so two equations:

$$\mathbf{a}_1^T(\mathbf{b} - A\hat{\mathbf{x}}) = 0, \qquad \mathbf{a}_2^T(\mathbf{b} - A\hat{\mathbf{x}}) = 0$$

Stack them into a matrix equation — $\mathbf{a}_1^T$ and $\mathbf{a}_2^T$ are exactly the rows of $A^T$ — and it comes out just right:

$$A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$$

Two remarks before solving. First: in the very first problem, $A$ had one column, little $\mathbf{a}$ — change capital $A$ to little $\mathbf{a}$ and this is the equation we solved on the line. Second: which of the four subspaces is $\mathbf{e}$ in? The equation says $A^T\mathbf{e} = \mathbf{0}$, so $\mathbf{e}$ is in the null space of $A^T$.

The three formulas in n dimensions

Rewrite the equation in its famous form:

The three answers, matching the three from the line:

$$\hat{\mathbf{x}} = (A^TA)^{-1}A^T\mathbf{b}, \qquad \mathbf{p} = A\hat{\mathbf{x}} = A(A^TA)^{-1}A^T\mathbf{b}, \qquad P = A(A^TA)^{-1}A^T$$

The projection matrix looks a little messy but it’s not bad — it’s the “magic combination,” the $n$-dimensional version of $\mathbf{a}\mathbf{a}^T/\mathbf{a}^T\mathbf{a}$. In more dimensions we’re not allowed to just divide, so inverse replaces the division.

Now the first thing that occurs to you is something bad. Why not split the inverse of the product, $(A^TA)^{-1} = A^{-1}(A^T)^{-1}$? Then $P = A\,A^{-1}(A^T)^{-1}A^T = I$ — the identity! Strang writes it on the board but warns: “don’t take the videotape quite so carefully.” The step is not allowed: $A$ is not square — it has too many rows, just a couple of columns — so $A^{-1}$ doesn’t exist. $A^TA$ is square and invertible, but it can’t be pulled apart.

Except… suppose $A$ were square and invertible. Then its column space is all of $\mathbb{R}^n$, and projecting $\mathbf{b}$ onto the whole space should give back $\mathbf{b}$ itself — the projection matrix should be the identity. And that’s exactly what the split-apart computation gives: $P = I$ is the correct answer in that case. For a genuine subspace, stay with the full formula.

Do the two projection properties still hold? $P^T = P$: transpose the product — the symmetric middle factor $(A^TA)^{-1}$ stays symmetric, the outer $A$ and $A^T$ swap ends, and you’re back to $P$. And $P^2 = P$ — writing it out gives “eight $A$‘s in a row, which is quite obscene,” but put the parentheses in good places: an $A^TA$ sits next to its inverse in the middle, all that stuff goes, and what’s left is $P$ again. Geometrically it had to work: the first projection pops you onto the column space, the second leaves you where you are.

Least squares: fitting a line to three points

Now to use the formulas. When do you have too many equations and still want a best answer? The most important, most common example: fitting points by a straight line.

Take three data points: at $t = 1, 2, 3$ the measurements are $b = 1, 2, 2$. They lie close to a line but not on one. We want the best line $b = C + Dt$ — the one whose errors at the three points are as small as we can get them.

Today was all letters; numbers next time — the next lecture carries this example through to the actual best line.

Problems

Work these before revealing the solutions — the lecture’s three formulas are all you need.

Problem 15.1 Projection onto a line

Project $\mathbf{b} = \begin{bmatrix} 1 \\ 2 \\ 6 \end{bmatrix}$ onto the line through $\mathbf{a} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$. Find $x$, the projection $\mathbf{p}$, and the error $\mathbf{e}$, and verify that $\mathbf{e}$ is perpendicular to $\mathbf{a}$.

Show solution

$$x = \frac{\mathbf{a}^T\mathbf{b}}{\mathbf{a}^T\mathbf{a}} = \frac{1 + 2 + 6}{1 + 1 + 1} = \frac{9}{3} = 3, \qquad \mathbf{p} = 3\mathbf{a} = \begin{bmatrix} 3 \\ 3 \\ 3 \end{bmatrix}$$

The error is

$$\mathbf{e} = \mathbf{b} - \mathbf{p} = \begin{bmatrix} -2 \\ -1 \\ 3 \end{bmatrix}$$

and $\mathbf{a}^T\mathbf{e} = -2 - 1 + 3 = 0$: perpendicular, as the geometry demands.

Problem 15.2 Rank-one projection matrix

Compute the projection matrix $P = \dfrac{\mathbf{a}\mathbf{a}^T}{\mathbf{a}^T\mathbf{a}}$ for $\mathbf{a} = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}$. Check that $P$ is symmetric, that $P^2 = P$, and give its rank and column space.

Show solution

$\mathbf{a}^T\mathbf{a} = 1 + 4 + 4 = 9$, and the column-times-row product gives

$$P = \frac{1}{9}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{bmatrix}$$

Symmetric: yes — the $(i,j)$ entry $a_i a_j / 9$ equals the $(j,i)$ entry.

$P^2 = P$: compute $(\mathbf{a}\mathbf{a}^T)(\mathbf{a}\mathbf{a}^T) = \mathbf{a}(\mathbf{a}^T\mathbf{a})\mathbf{a}^T = 9\,\mathbf{a}\mathbf{a}^T$, so $P^2 = \dfrac{9\,\mathbf{a}\mathbf{a}^T}{81} = \dfrac{\mathbf{a}\mathbf{a}^T}{9} = P$.

Rank and column space: every column is a multiple of $\mathbf{a}$, so the rank is $1$ and the column space is the line through $\mathbf{a}$ — exactly the line we project onto.

Problem 15.3 Projection onto a plane

Let

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

Project $\mathbf{b}$ onto the column space of $A$: find $\hat{\mathbf{x}}$, the projection $\mathbf{p}$, and the error $\mathbf{e}$, and check that $\mathbf{e}$ is perpendicular to both columns of $A$.

Show solution

Form the normal equation $A^TA\hat{\mathbf{x}} = A^T\mathbf{b}$:

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

Solve $3\hat{x}_1 + 3\hat{x}_2 = 6$ and $3\hat{x}_1 + 5\hat{x}_2 = 0$: subtracting, $2\hat{x}_2 = -6$, so $\hat{x}_2 = -3$ and $\hat{x}_1 = 5$.

$$\hat{\mathbf{x}} = \begin{bmatrix} 5 \\ -3 \end{bmatrix}, \qquad \mathbf{p} = A\hat{\mathbf{x}} = \begin{bmatrix} 5 \\ 2 \\ -1 \end{bmatrix}, \qquad \mathbf{e} = \mathbf{b} - \mathbf{p} = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix}$$

Perpendicularity: against column one, $1 - 2 + 1 = 0$; against column two, $0 - 2 + 2 = 0$. The error is in $N(A^T)$, perpendicular to the whole plane.

Problem 15.4 Extreme cases of P

Using $P = A(A^TA)^{-1}A^T$, show two facts without choosing numbers: (a) if $\mathbf{b}$ is already in the column space of $A$, then $P\mathbf{b} = \mathbf{b}$; (b) if $\mathbf{b}$ is perpendicular to the column space of $A$, then $P\mathbf{b} = \mathbf{0}$.

Show solution

(a) If $\mathbf{b}$ is in the column space, then $\mathbf{b} = A\mathbf{x}$ for some $\mathbf{x}$. Then

$$P\mathbf{b} = A(A^TA)^{-1}A^TA\mathbf{x} = A\mathbf{x} = \mathbf{b},$$

since $(A^TA)^{-1}$ cancels $A^TA$. A vector already in the subspace projects to itself.

(b) Perpendicular to the column space means $\mathbf{b}$ is in $N(A^T)$, so $A^T\mathbf{b} = \mathbf{0}$. Then

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

A vector with no component in the subspace projects to zero.

Problem 15.5 Best line by least squares

Find the best straight line $b = C + Dt$ through the points $(0, 1)$, $(1, 1)$, and $(2, 3)$, by setting up the unsolvable system $A\mathbf{x} = \mathbf{b}$ and solving the normal equation $A^TA\hat{\mathbf{x}} = A^T\mathbf{b}$.

Show solution

Asking the line to pass through each point:

$$\begin{aligned} C \phantom{{}+ 0D} &= 1 \\ C + D &= 1 \\ C + 2D &= 3 \end{aligned} \qquad\Longrightarrow\qquad A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 1 \\ 1 \\ 3 \end{bmatrix}$$

No solution — so multiply both sides by $A^T$:

$$A^TA = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, \qquad A^T\mathbf{b} = \begin{bmatrix} 5 \\ 7 \end{bmatrix}$$

From $3C + 3D = 5$ and $3C + 5D = 7$: subtracting gives $2D = 2$, so $D = 1$ and $C = \frac{2}{3}$. The best line is

$$b = \tfrac{2}{3} + t$$

Check the errors at $t = 0, 1, 2$: predictions $\frac{2}{3}, \frac{5}{3}, \frac{8}{3}$, errors $\frac{1}{3}, -\frac{2}{3}, \frac{1}{3}$. They sum to zero — the error vector is perpendicular to the all-ones column of $A$, just as the projection picture requires.