Orthogonality and Least Squares

Discover: eight equations, two unknowns

Meet eight researchers, surveyed for two numbers each: cups of coffee per day ($x$) and lines of code written per day, in tens ($y$). You'll meet them again in Neural Networks from First Principles, where gradient descent takes about two thousand small steps to find the best straight line $\hat{y} = wx + b$ through their data. Here you'll find the same line in one move, and you'll see why it's the best one.

Ask for a line through all eight points and you are asking for eight equations to hold at once, one per researcher, in only two unknowns $w$ and $b$. Stack them, as Chamber 5 taught you, into a single matrix equation $X\boldsymbol{\theta} = \mathbf{y}$:

The first column of $X$ holds the $x$ values, and the column of ones multiplies $b$. Row $i$ says $w x_i + b = y_i$. The data is noisy, so no line hits all eight points, and this system has no solution. Elimination would grind to a contradiction like $0 = 1.3$.

So the real question is: what is the best wrong answer? Statisticians settled it long ago, and they write the answer like this:

Their $\hat{\boldsymbol{\beta}}$ (read “beta hat”) is our $\boldsymbol{\theta}$, their $\mathbf{Y}$ is our $\mathbf{y}$, and the prime $'$ is an older way to write the transpose $^\top$. By the end of this chamber you'll derive this formula from a single picture, a right angle, and you'll know why the matrix $\mathbf{X}'\mathbf{X}$ appears in it. The same paper then changes one symbol in it to invent ridge regression, which you'll decode near the end.

Learn: orthogonal vectors and orthogonal subspaces

Chamber 2 gave you the test for a right angle: two vectors are orthogonal when their dot product is zero. We write

and read $\perp$ as “is perpendicular to” or “is orthogonal to”. For example $(1, 2) \perp (2, -1)$, because $2 - 2 = 0$.

The idea scales up from vectors to whole subspaces. Two subspaces $V$ and $W$ are orthogonal when every vector in $V$ is perpendicular to every vector in $W$. The floor of a room and the line of a vertical pole standing on it are orthogonal subspaces of $\mathbb{R}^3$. The orthogonal complement $V^\perp$ (read “V perp”) is everything perpendicular to $V$. The complement of the floor is the vertical line, and the complement of the vertical line is the floor.

Chamber 6 introduced four subspaces of a matrix $A$. Orthogonality is the thread that ties them into pairs, and one pairing drives this whole chamber:

The left null space is perpendicular to the column space. A vector $\mathbf{y}$ satisfies $A^\top\mathbf{y} = \mathbf{0}$ exactly when $\mathbf{y}$ is perpendicular to every column of $A$.

The reason is short enough to see in one line. Row $j$ of $A^\top$ is column $j$ of $A$, call it $\mathbf{a}_j$, so the $j$-th entry of $A^\top\mathbf{y}$ is $\mathbf{a}_j^\top\mathbf{y}$. The whole vector $A^\top\mathbf{y}$ is zero exactly when every one of these dot products is zero, that is, when $\mathbf{y} \perp \mathbf{a}_j$ for every column. And a vector perpendicular to each column is perpendicular to every combination of columns: $(c_1\mathbf{a}_1 + c_2\mathbf{a}_2)^\top\mathbf{y} = c_1\mathbf{a}_1^\top\mathbf{y} + c_2\mathbf{a}_2^\top\mathbf{y} = 0$. So $N(A^\top) = C(A)^\perp$, where $C(A)$ is the column space and $N(A^\top)$ the left null space. The same argument with rows shows that the null space $N(A)$ is perpendicular to the row space.

Keep “$A^\top\mathbf{y} = \mathbf{0}$ means $\mathbf{y}$ is perpendicular to the columns” in your pocket. It is the whole secret of least squares.

Learn: orthonormal bases

Some bases are much nicer than others. A set of vectors $\mathbf{q}_1, \ldots, \mathbf{q}_n$ is orthonormal when each has length 1 and each pair is perpendicular. The Kronecker delta from Mathematics for Machine Learning says it in one line:

Stack the vectors as the columns of a matrix $Q$. Entry $(i, j)$ of $Q^\top Q$ is row $i$ of $Q^\top$ times column $j$ of $Q$, which is exactly $\mathbf{q}_i^\top\mathbf{q}_j$. So the whole table of dot products collapses into one statement:

Why is this so pleasant? Coordinates become dot products. To write $\mathbf{x} = c_1\mathbf{q}_1 + \cdots + c_n\mathbf{q}_n$, dot both sides with $\mathbf{q}_i$. Every term but one vanishes, and $c_i = \mathbf{q}_i^\top\mathbf{x}$. No elimination, no inverse. For example, $\mathbf{q}_1 = (\tfrac{3}{5}, \tfrac{4}{5})$ and $\mathbf{q}_2 = (-\tfrac{4}{5}, \tfrac{3}{5})$ are orthonormal, and $\mathbf{x} = (2, 1)$ has coordinates $c_1 = \tfrac{6}{5} + \tfrac{4}{5} = 2$ and $c_2 = -\tfrac{8}{5} + \tfrac{3}{5} = -1$. Check: $2\mathbf{q}_1 - \mathbf{q}_2 = (\tfrac{6}{5} + \tfrac{4}{5}, \tfrac{8}{5} - \tfrac{3}{5}) = (2, 1)$.

When $Q$ is square it is called an orthogonal matrix (the standard, slightly unlucky name: its columns are orthonormal). Then $Q^\top Q = I$ says that $Q^\top$ is the inverse of $Q$. Rotations, reflections and permutation matrices are all orthogonal matrices, and inverting any of them costs nothing but a transpose.

Orthogonal matrices never distort anything. Here is the proof that they preserve length.

Claim. If $Q^\top Q = I$, then $\|Q\mathbf{x}\| = \|\mathbf{x}\|$ for every vector $\mathbf{x}$.

Proof. Squared lengths are dot products, and the transpose of a product reverses the order, $(Q\mathbf{x})^\top = \mathbf{x}^\top Q^\top$. So

Both lengths are non-negative, so taking square roots gives $\|Q\mathbf{x}\| = \|\mathbf{x}\|$. $\blacksquare$

The same computation with two different vectors shows $(Q\mathbf{x})^\top(Q\mathbf{y}) = \mathbf{x}^\top\mathbf{y}$: dot products, and therefore angles, survive too.

Learn: projecting onto a line

Now the central picture. Take a line through the origin in the direction $\mathbf{a}$, and a vector $\mathbf{b}$ that is not on it. Which point of the line is closest to $\mathbf{b}$?

Think of the myth's shaft of light. The shadow of $\mathbf{b}$ falls straight onto the line, at the foot of the perpendicular. Call that point $\mathbf{p}$, the projection of $\mathbf{b}$ onto $\mathbf{a}$, sometimes written $\operatorname{proj}_{\mathbf{a}}(\mathbf{b})$ (“the projection of b onto a”). The gap $\mathbf{e} = \mathbf{b} - \mathbf{p}$ is the error, and the picture says it meets the line at a right angle. Chamber 2 previewed the answer. Here is the derivation in full.

1. 1

   Name the unknown

   The point $\mathbf{p}$ lies on the line, so it is some multiple of $\mathbf{a}$: $\mathbf{p} = \hat{x}\,\mathbf{a}$ (read “x hat times a”). We need the number $\hat{x}$.

2. 2

   Write down the right angle

   The error $\mathbf{e} = \mathbf{b} - \hat{x}\,\mathbf{a}$ must be perpendicular to $\mathbf{a}$: $\;\mathbf{a}^\top(\mathbf{b} - \hat{x}\,\mathbf{a}) = 0$.

3. 3

   Expand and solve

   Distributing gives $\mathbf{a}^\top\mathbf{b} - \hat{x}\,\mathbf{a}^\top\mathbf{a} = 0$, so $\hat{x} = \dfrac{\mathbf{a}^\top\mathbf{b}}{\mathbf{a}^\top\mathbf{a}}$. This is allowed because $\mathbf{a}^\top\mathbf{a} = \|\mathbf{a}\|^2$ is not zero.

4. 4

   Assemble the projection

   $\mathbf{p} = \hat{x}\,\mathbf{a} = \mathbf{a}\,\dfrac{\mathbf{a}^\top\mathbf{b}}{\mathbf{a}^\top\mathbf{a}}$. Moving the scalar around, $\mathbf{p} = \dfrac{\mathbf{a}\mathbf{a}^\top}{\mathbf{a}^\top\mathbf{a}}\,\mathbf{b} = P\mathbf{b}$, with the projection matrix $P = \dfrac{\mathbf{a}\mathbf{a}^\top}{\mathbf{a}^\top\mathbf{a}}$.

A worked example. Let $\mathbf{a} = (1, 2)$ and $\mathbf{b} = (3, 1)$. Then $\mathbf{a}^\top\mathbf{b} = 3 + 2 = 5$ and $\mathbf{a}^\top\mathbf{a} = 5$, so $\hat{x} = 1$ and $\mathbf{p} = (1, 2)$. The error is $\mathbf{e} = (2, -1)$, and indeed $\mathbf{a}^\top\mathbf{e} = 2 - 2 = 0$. The matrix is

Notice three things. $P$ is the outer product $\mathbf{a}\mathbf{a}^\top$ scaled down, so it has rank 1, just like the $\mathbf{u}\mathbf{v}^\top$ matrices of Chamber 6: everything lands on one line. $P$ is symmetric. And $P^2 = P$ (read “P squared equals P”): once a vector is on the line, projecting it again leaves it where it is. Try multiplying $P$ by itself to see it happen.

Learn: why the perpendicular is the shortest way

The picture makes it believable that the foot of the perpendicular is the closest point. Mathematics wants “always”, so here is the proof. It works for a line, a plane, or any subspace, and it uses nothing but Pythagoras.

Claim. Let $S$ be a subspace, $\mathbf{b}$ any vector, and $\mathbf{p}$ a point of $S$ whose error $\mathbf{b} - \mathbf{p}$ is perpendicular to every vector in $S$. Then $\mathbf{p}$ is the closest point of $S$ to $\mathbf{b}$: $\|\mathbf{b} - \mathbf{q}\| \ge \|\mathbf{b} - \mathbf{p}\|$ for every $\mathbf{q}$ in $S$, with equality only when $\mathbf{q} = \mathbf{p}$.

Proof. Let $\mathbf{q}$ be any point of $S$. Split the path from $\mathbf{q}$ to $\mathbf{b}$ at $\mathbf{p}$:

Both $\mathbf{p}$ and $\mathbf{q}$ lie in the subspace $S$, so their difference $\mathbf{p} - \mathbf{q}$ does too. By assumption $\mathbf{b} - \mathbf{p}$ is perpendicular to everything in $S$, so the two pieces are perpendicular: $(\mathbf{b} - \mathbf{p})^\top(\mathbf{p} - \mathbf{q}) = 0$. Expanding the squared length, the cross terms are exactly this dot product (twice), so they vanish:

The last term is a squared length, so it is never negative. Therefore $\|\mathbf{b} - \mathbf{q}\|^2 \ge \|\mathbf{b} - \mathbf{p}\|^2$, and equality forces $\|\mathbf{p} - \mathbf{q}\| = 0$, that is, $\mathbf{q} = \mathbf{p}$. $\blacksquare$

Read the anatomy. The claim has a hypothesis (the error is perpendicular to $S$) and a conclusion (closest point). The one idea is to split $\mathbf{b} - \mathbf{q}$ into a perpendicular piece and a piece inside $S$. Then Pythagoras does the rest: the right triangle with corners $\mathbf{b}$, $\mathbf{p}$ and $\mathbf{q}$ has hypotenuse $\mathbf{b} - \mathbf{q}$, and a hypotenuse is never shorter than a leg.

Learn: projecting onto a subspace

Now replace the line by the column space of a matrix. Let $A$ be $m \times n$ with independent columns $\mathbf{a}_1, \ldots, \mathbf{a}_n$, and let $\mathbf{b}$ be a vector in $\mathbb{R}^m$. The closest point of $C(A)$ to $\mathbf{b}$ is some combination of the columns, $\mathbf{p} = A\hat{\mathbf{x}}$. By the proof above, it's the point whose error is perpendicular to the whole column space. The derivation follows the line case step for step.

1. 1

   Name the unknowns

   $\mathbf{p} = A\hat{\mathbf{x}}$ for an unknown vector of weights $\hat{\mathbf{x}} \in \mathbb{R}^n$ (read “x hat”). The error is $\mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}}$.

2. 2

   Write down the right angles

   $\mathbf{e}$ must be perpendicular to every column: $\mathbf{a}_1^\top\mathbf{e} = 0, \ldots, \mathbf{a}_n^\top\mathbf{e} = 0$. These $n$ dot products are the entries of $A^\top\mathbf{e}$, so all of them at once read $A^\top(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$.

3. 3

   Rearrange: the normal equations

   Distribute and move one term across: $A^\top A\,\hat{\mathbf{x}} = A^\top\mathbf{b}$. These are the normal equations (“normal” is an old word for perpendicular). They are $n$ equations in $n$ unknowns, a square system.

4. 4

   Solve

   When the columns of $A$ are independent, the square matrix $A^\top A$ is invertible (you'll assemble the proof in Your turn). So $\hat{\mathbf{x}} = (A^\top A)^{-1}A^\top\mathbf{b}$.

5. 5

   Project

   $\mathbf{p} = A\hat{\mathbf{x}} = A(A^\top A)^{-1}A^\top\mathbf{b} = P\mathbf{b}$, with the projection matrix $P = A(A^\top A)^{-1}A^\top$.

That is the formula from the Discover section, with $A = \mathbf{X}$, $\mathbf{b} = \mathbf{Y}$ and $\hat{\mathbf{x}} = \hat{\boldsymbol{\beta}}$. It came from one idea: the error is perpendicular to the columns. With a single column $\mathbf{a}$, the matrix $A^\top A$ is the number $\mathbf{a}^\top\mathbf{a}$ and everything reduces to the line case.

Like the line version, $P$ is symmetric and satisfies $P^2 = P$. You'll prove both in Your turn.

Learn: least squares is a projection

Back to the eight researchers. For a candidate line $\boldsymbol{\theta} = (w, b)$, the vector of predictions is $X\boldsymbol{\theta}$, and the sum of squared errors is

That is the squared distance in $\mathbb{R}^8$ between the data $\mathbf{y}$ and the point $X\boldsymbol{\theta}$. As $\boldsymbol{\theta}$ varies, $X\boldsymbol{\theta}$ sweeps out the column space $C(X)$, a plane in $\mathbb{R}^8$. So the best line is the closest point of that plane to $\mathbf{y}$, which is the projection. Linear regression is a projection, and its coefficients solve the normal equations $X^\top X\hat{\boldsymbol{\theta}} = X^\top\mathbf{y}$. Statistics writes the same thing as $\mathbf{X}\boldsymbol{\beta} \approx \mathbf{Y}$ and linear algebra as $A\mathbf{x} \approx \mathbf{b}$: one problem, three dialects.

Let's do a small one completely by hand, with three points $(1, 1)$, $(2, 2)$ and $(3, 2)$. It is the example Gilbert Strang works in the lecture recommended below.

The normal equations are $14w + 6b = 11$ and $6w + 3b = 5$. Doubling the second gives $12w + 6b = 10$, and subtracting it from the first leaves $2w = 1$. So $w = \tfrac{1}{2}$ and $b = \tfrac{2}{3}$: the best line is $\hat{y} = \tfrac{1}{2}x + \tfrac{2}{3}$. Its predictions are $(\tfrac{7}{6}, \tfrac{5}{3}, \tfrac{13}{6})$ and the residuals are

Check the right angles. Against the column of ones: $-\tfrac{1}{6} + \tfrac{1}{3} - \tfrac{1}{6} = 0$. Against the $x$ column: $-\tfrac{1}{6} + \tfrac{2}{3} - \tfrac{1}{2} = 0$. The residual is perpendicular to the column space, as promised.

Now it's your turn to be the projection. Tune the line by hand until you're within 1% of the least-squares error, then look at the residual.

In the lab you saw a line whose error was almost minimal but whose residual was not orthogonal to the columns: $X^\top\mathbf{r}$ was small, not zero. The right angle is what singles out the exact optimum. You also met a consequence worth remembering. Because the column of ones is in $C(X)$, the least-squares residuals of any line with an intercept sum to zero, and the fitted line always passes through the mean point $(\bar{x}, \bar{y})$.

Learn: Gram–Schmidt and QR

Projections are easiest of all when the columns are orthonormal. If $A = Q$ with $Q^\top Q = I$, the normal equations $Q^\top Q\,\hat{\mathbf{x}} = Q^\top\mathbf{b}$ collapse to $\hat{\mathbf{x}} = Q^\top\mathbf{b}$, and the projection matrix becomes $P = QQ^\top$. No inverse anywhere. So it is worth knowing how to make an orthonormal basis out of any independent vectors. The recipe is the Gram–Schmidt process, and it uses nothing but projections onto lines.

The idea: take the vectors one at a time. From each new vector, subtract its projections onto the directions you've already built. What's left is perpendicular to all of them. Then scale it to length 1.

Here it is on $\mathbf{a}_1 = (1, 1, 0)$ and $\mathbf{a}_2 = (1, 0, 1)$.

1. 1

   First direction: just normalise

   $\|\mathbf{a}_1\| = \sqrt{2}$, so $\mathbf{q}_1 = \tfrac{1}{\sqrt{2}}(1, 1, 0)$.

2. 2

   Second direction: remove the shadow on the first

   $\mathbf{q}_1^\top\mathbf{a}_2 = \tfrac{1}{\sqrt{2}}$, so $\mathbf{v}_2 = \mathbf{a}_2 - \tfrac{1}{\sqrt{2}}\,\mathbf{q}_1 = (1, 0, 1) - (\tfrac{1}{2}, \tfrac{1}{2}, 0) = (\tfrac{1}{2}, -\tfrac{1}{2}, 1)$. Check: $\mathbf{q}_1^\top\mathbf{v}_2 \propto \tfrac{1}{2} - \tfrac{1}{2} + 0 = 0$.

3. 3

   Normalise

   $\|\mathbf{v}_2\| = \sqrt{\tfrac{1}{4} + \tfrac{1}{4} + 1} = \sqrt{\tfrac{3}{2}}$, so $\mathbf{q}_2 = \tfrac{1}{\sqrt{6}}(1, -1, 2)$.

$\mathbf{q}_1$ and $\mathbf{q}_2$ span the same plane as $\mathbf{a}_1$ and $\mathbf{a}_2$, but now they meet at a right angle and have unit length.

Record the bookkeeping and you get a factorisation. Each $\mathbf{a}_k$ is a combination of $\mathbf{q}_1, \ldots, \mathbf{q}_k$ only, never of later ones, so

This QR factorisation is how careful software does least squares. Substituting $A = QR$ into the normal equations and cancelling (both $R^\top$ and $R$ are invertible here) leaves $R\hat{\mathbf{x}} = Q^\top\mathbf{b}$: a triangular system you solve by back substitution, as in Chamber 5.

import numpy as np

def gram_schmidt(A):
    """Orthonormalise the columns of A (assumed independent)."""
    Q = np.zeros(A.shape)
    for k in range(A.shape[1]):
        v = A[:, k].astype(float)
        for j in range(k):
            v = v - (Q[:, j] @ A[:, k]) * Q[:, j]   # remove the shadow on q_j
        Q[:, k] = v / np.linalg.norm(v)
    return Q

A = np.array([[1, 1], [1, 0], [0, 1]])
Q = gram_schmidt(A)
print(np.round(Q.T @ Q, 10))   # the identity: orthonormal columns

Read beyond the course

Each of these picks up exactly where this chamber stops. All are free.

Papers and lectures

Hoerl and Kennard's 1970 paper is thirteen pages long, and you can read the important parts today. It is on the publisher's website, where you may need library access (most universities provide it). Start with the abstract and Section 0, one page of plain English about why least squares misbehaves when predictors are correlated. In Section 1, read Eq. (1.1), which you now know how to derive, and Eq. (1.2), the residual sum of squares, which is your $\|\mathbf{y} - X\hat{\boldsymbol{\theta}}\|^2$. Then read Section 2 up to Eq. (2.8): the ridge estimator and the fact that it is shorter than the least-squares one. Skip Sections 4 and 5, which need expectations and eigenvalues (Chamber 8 covers the eigenvalues). Finish with the bullet list in Section 7 and the conclusions in Section 8.

Watch

Gilbert Strang's classic 18.06 lectures. In the first, watch him derive $A^\top(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$ from the same right angle you used here. In the second, he fits the line through $(1, 1)$, $(2, 2)$ and $(3, 2)$ and draws both pictures at once: the points and line in the plane, and the projection in $\mathbb{R}^3$. Pause each time before he writes a formula and try to say it first.

Your turn

Match the notation to its meaning and to its code, assemble one proof and write another, then solve three problems. The last one applies Hoerl and Kennard's estimator to a dataset built to fool least squares.

Proofs

The puzzle proves the fact the normal equations rely on: independent columns make $A^\top A$ invertible. Then prove the two properties of $P$ yourself.

Code it up