3.2 Projection and Orthogonality – Introduction to Data Mining

Orthogonality

Two vectors are orthogonal when their dot product is zero. In two or three dimensions this is exactly perpendicularity; in higher dimensions we take it as the definition.

\mathbf{u} \perp \mathbf{v} \quad\Longleftrightarrow\quad \mathbf{u}^\top\mathbf{v} = 0

Projecting onto a line

Given a vector \mathbf{b} and a direction \mathbf{a}, which multiple of \mathbf{a} lies closest to \mathbf{b}?

Write the candidate as \hat{x}\mathbf{a}. The error \mathbf{b} - \hat{x}\mathbf{a} is smallest exactly when it is orthogonal to \mathbf{a}:

\mathbf{a}^\top(\mathbf{b} - \hat{x}\mathbf{a}) = 0 \quad\Longrightarrow\quad \hat{x} = \frac{\mathbf{a}^\top\mathbf{b}}{\mathbf{a}^\top\mathbf{a}}

so the projection of \mathbf{b} onto the line through \mathbf{a} is

\mathbf{p} = \frac{\mathbf{a}^\top\mathbf{b}}{\mathbf{a}^\top\mathbf{a}}\,\mathbf{a}.

The residual \mathbf{b} - \mathbf{p} should be orthogonal to \mathbf{a}. Check it rather than trust it:

Notice what \mathbf{p} came out to be here: \mathbf{a} was the vector of all ones, and the projection is the mean of \mathbf{b} repeated. Averaging is a projection. That is not a coincidence, and it is why an intercept-only regression predicts the mean.

Projecting onto a subspace

Now let A be an m \times n matrix whose columns span some subspace of \mathbb{R}^m—its column space, written \mathcal{C}(A). Given \mathbf{b} \in \mathbb{R}^m, which vector in \mathcal{C}(A) is closest to \mathbf{b}?

Every element of the column space is A\mathbf{x} for some \mathbf{x}. The same argument applies: the residual must be orthogonal to every column of A, which is to say

A^\top(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0} \quad\Longrightarrow\quad A^\top A\,\hat{\mathbf{x}} = A^\top\mathbf{b}.

These are the normal equations. When A^\top A is invertible,

\hat{\mathbf{x}} = (A^\top A)^{-1}A^\top\mathbf{b}, \qquad \mathbf{p} = A\hat{\mathbf{x}} = \underbrace{A(A^\top A)^{-1}A^\top}_{P}\,\mathbf{b}.

P is the projection matrix onto \mathcal{C}(A).

A projection matrix has two properties worth verifying, because together they are what it means to be a projection: it is symmetric, and applying it twice does nothing new.

Least squares is a projection

The matrix A above was not arbitrary. Its first column is all ones and its second counts 0,1,2,3—it is the design matrix for fitting a straight line to four points. Solving the normal equations is fitting that line.

So “fit a line by least squares” and “project the data onto the column space of the design matrix” are the same sentence in two languages. The fitted values are the projection; the residuals are what is left over, and they are orthogonal to every predictor:

That last check is worth remembering. Residuals orthogonal to the predictors is not a diagnostic you should hope for; it is a consequence of how the coefficients were chosen. If a residual plot shows structure against a predictor already in the model, something is wrong with your code, not with your data.

Why you will meet this again

On Nov 3 we look at linear regression as prediction. Two things carry over directly:

The fitted values \hat{\mathbf{y}} = P\mathbf{y} are a projection, and P is often called the hat matrix because it puts the hat on \mathbf{y}.
When the columns of A are nearly parallel, A^\top A is close to singular, (A^\top A)^{-1} is enormous, and the coefficients become wild while the fit stays fine. That is multicollinearity, and it is what ridge regression exists to fix. The SVD is what makes the fix legible.

What makes a matrix a projection

Let A be m\times n with m > n and with linearly independent columns, and let

P = A(A^\top A)^{-1}A^\top.

Which of the following statements are true? Select all that apply.

P^2 = P.P^\top = P.P is invertible.\operatorname{tr}(P) = n.

P^2 = P (true). Substituting, P^2 = A(A^\top A)^{-1}A^\top A(A^\top A)^{-1}A^\top = A(A^\top A)^{-1}A^\top = P: the middle A^\top A cancels its own inverse. Geometrically, once a vector has been projected it already lies in \mathcal{C}(A), so projecting again moves nothing.

P^\top = P (true). A^\top A is symmetric, so its inverse is symmetric, and transposing the product reverses the factors back into the same expression. Symmetry plus idempotence is not a coincidence—those two properties together characterize orthogonal projection matrices.

P is invertible (false). P maps all of \mathbb{R}^m into the n-dimensional subspace \mathcal{C}(A), so with m > n it crushes an (m-n)-dimensional space to zero and cannot be inverted. Every vector orthogonal to \mathcal{C}(A) is sent to \mathbf{0}.

\operatorname{tr}(P) = n (true). Idempotence forces every eigenvalue to satisfy \lambda^2 = \lambda, so each is 0 or 1; the trace, being the sum of the eigenvalues, simply counts the 1s, and that count is \dim\mathcal{C}(A) = \operatorname{rank}(A) = n. This is where the n in the residual degrees of freedom m - n comes from.

Orthogonal columns make everything easier

If the columns of A are mutually orthogonal, A^\top A is diagonal and the normal equations decouple: each coefficient can be computed independently of the others.

This is the entire motivation for the QR decomposition in 3.1: rewrite A = QR with Q having orthonormal columns, and the projection collapses to P = QQ^\top, with no inverse to compute.

Same projection, computed without ever forming A^\top A—which matters, because forming A^\top A squares the conditioning of the problem.

Exercises

Exercise 1: project onto a line

Project \mathbf{b} = (2, 3, 5) onto the line through \mathbf{a} = (1, 0, 1). Predict the residual’s dot product with \mathbf{a} before you compute anything.

Exercise 2: projecting something already in the subspace

b lies in \mathcal{C}(A) by construction. Reason out what P\mathbf{b} must be before you compute it, then compute it.

Exercise 3: when A^\top A is singular

A3 has a third column equal to the sum of the first two, so np.linalg.matrix_rank(A3) is 2, not 3. The column space is unchanged, so the projection P must be unchanged too—yet np.linalg.inv(A3.T @ A3) raises LinAlgError. Both statements are true at once. Build P in a way that still works.

Hint: the Moore-Penrose pseudoinverse np.linalg.pinv is defined for every matrix, singular or not.

Exercise 4: averaging is a projection

A1 is a single all-ones column. Project b onto its column space and confirm what the prose above claimed: the projection is the mean of b, repeated.

P1 = A1 @ np.linalg.inv(A1.T @ A1) @ A1.T
answer = P1 @ b

Here A_1^\top A_1 = 5 (the number of observations) and A_1^\top\mathbf{b} is the sum, so P_1 is the 5\times5 matrix with every entry 1/5 and P_1\mathbf{b} is the mean repeated. Centring a column in week 2—X - X.mean(axis=0)—was therefore subtracting a projection, which is the observation 3.3 builds PCA on.

Exercise 5: the trace counts dimensions

M = I - P is the residual maker: it sends \mathbf{b} to its residual. It is a projection too, onto the orthogonal complement of \mathcal{C}(A). Compute its trace, and say what number you expect before you look.