Orthogonal Projection

Every machine learning algorithm that fits a model to data is, at its mathematical core, solving a projection problem. When you train a linear regression model, you're not just "fitting a line"—you're finding the orthogonal projection of your target vector onto the column space of your feature matrix. When principal component analysis reduces dimensions, it's projecting data onto lower-dimensional subspaces that capture maximum variance.

Orthogonal projection is the mathematical operation that finds the closest point in a subspace to a given point. This seemingly abstract geometric operation is the engine powering fundamental ML techniques:

• Linear Regression: Projects the target vector onto the column space spanned by features
• PCA: Projects data onto principal component subspaces
• Gram-Schmidt Orthogonalization: Builds orthonormal bases through sequential projections
• Signal Processing: Decomposes signals into components via projection onto basis functions

Understanding projection at a deep, geometric level transforms how you understand model fitting. You'll see that least squares isn't an arbitrary choice—it's the mathematically natural consequence of seeking the closest approximation in a geometric sense.

Before diving into formulas, let's build geometric intuition. Consider a simple 3D scenario: you have a vector b in three-dimensional space, and a plane passing through the origin (a 2D subspace). What point on the plane is closest to b?

Intuitively, you'd drop a perpendicular from b to the plane. The foot of that perpendicular—let's call it p—is the orthogonal projection of b onto the plane.

Key geometric properties:

1. Perpendicularity: The error vector (b - p) is perpendicular to every vector in the plane
2. Uniqueness: There's exactly one closest point—the projection is unique
3. Distance Minimization: The projection minimizes the Euclidean distance from b to any point in the subspace

The perpendicularity condition is crucial. If the error weren't perpendicular, you could "slide" along the plane to find a closer point—contradicting that p is the closest. The Pythagorean theorem guarantees this: any other point in the plane forms a right triangle with p and b, making it necessarily farther from b.

Generalizing to arbitrary subspaces:

This intuition extends to any subspace S of any dimension within any vector space. Given a vector b and a subspace S:

• The orthogonal projection proj_S(b) is the unique vector in S closest to b
• The error or residual is e = b - proj_S(b)
• The error is orthogonal to every vector in S: for all s ∈ S, we have e · s = 0

We write b = proj_S(b) + e, decomposing b into a component in S and a component orthogonal to S. This decomposition is unique and forms the foundation of approximation theory.

Let's start with the simplest case: projecting a vector b onto a line spanned by a single non-zero vector a. The projection must be a scalar multiple of a:

proj_a(b) = xa for some scalar x

To find x, we use the perpendicularity condition. The error b - xa must be perpendicular to a:

(b - xa) · a = 0

Expanding:

b · a - x(a · a) = 0

Solving for x:

x = (a · b) / (a · a) = (a · b) / ||a||²

Therefore, the projection formula is:

proj_a(b) = (a · b / a · a) · a = (aᵀb / aᵀa) · a

Important observations:

1. The Pythagorean Theorem holds: Since the projection and error are orthogonal: ||b||² = ||proj_a(b)||² + ||e||²

This is the Pythagorean theorem in action—the squared length of the hypotenuse equals the sum of squared lengths of the legs.

2. Scaling invariance of direction: If we scale a by a non-zero constant c, the projection doesn't change: proj_{ca}(b) = ((ca) · b / (ca) · (ca)) · (ca) = (c(a · b) / c²(a · a)) · (ca) = (a · b / a · a) · a = proj_a(b)

The projection depends only on the direction of the line, not the magnitude of the vector spanning it.

3. Normalized case: If a is a unit vector (||a|| = 1), the formula simplifies: proj_a(b) = (a · b)a

The scalar (a · b) is the signed length of the projection—positive if b has a component in the direction of a, negative if opposite.

Now consider projecting b onto a subspace S of dimension k, spanned by linearly independent vectors a₁, a₂, ..., aₖ. We can arrange these as columns of a matrix A = [a₁ | a₂ | ... | aₖ], so S = Col(A), the column space of A.

The projection must be expressible as a linear combination of the basis vectors:

proj_S(b) = x₁a₁ + x₂a₂ + ... + xₖaₖ = Ax

for some coefficient vector x ∈ ℝᵏ.

The orthogonality condition says the error b - Ax must be perpendicular to every vector in S. Since {a₁, ..., aₖ} spans S, it suffices to require:

aᵢ · (b - Ax) = 0 for all i = 1, ..., k

In matrix form:

Aᵀ(b - Ax) = 0

Expanding:

Aᵀb - AᵀAx = 0

AᵀAx** = Aᵀ**b****

These are the famous normal equations. If A has full column rank (columns are linearly independent), then AᵀA is invertible, and:

x = (AᵀA)⁻¹Aᵀb

The projection is:

proj_S(b) = A(AᵀA)⁻¹Aᵀb

Deriving the formula step by step:

Step 1: Set up the optimization problem We want the point p ∈ Col(A) that minimizes ||b - p||. Since p ∈ Col(A), we write p = Ax for some x.

Step 2: Apply the orthogonality condition The error e = b - Ax must be orthogonal to Col(A). This means e ⊥ aⱼ for each column aⱼ of A.

Step 3: Express orthogonality in matrix form The condition aⱼᵀe = 0 for all j can be written as Aᵀe = 0, or Aᵀ(b - Ax) = 0.

Step 4: Solve the normal equations Rearranging: AᵀAx = Aᵀb. If AᵀA is invertible: x = (AᵀA)⁻¹Aᵀb.

Step 5: The projection Substituting back: p = Ax = A(AᵀA)⁻¹Aᵀb.

The expression A(AᵀA)⁻¹Aᵀ is so fundamental that it has its own name: the projection matrix (or hat matrix in statistics). We'll explore its properties in depth on the next page.

The orthogonality principle is the cornerstone of projection theory. It states:

A vector p in subspace S is the orthogonal projection of b onto S if and only if the error (b - p) is orthogonal to every vector in S.

This is an if and only if statement—orthogonality both characterizes projections and is sufficient to identify them. Let's prove both directions:

Proof that the projection satisfies orthogonality:

Suppose p is the closest point in S to b. We want to show (b - p) ⊥ S.

Take any vector s ∈ S and consider p + ts for scalar t. This is also in S. The squared distance from b to p + ts is:

||b - (p + ts)||² = ||(b - p) - ts||² = ||b - p||² - 2t(b - p)·s + t²||s||²

Since p minimizes this distance, the derivative with respect to t at t=0 must be zero:

d/dt [||b - p||² - 2t(b - p)·s + t²||s||²] |_{t=0} = -2(b - p)·s = 0

Therefore (b - p)·s = 0 for all s ∈ S, proving orthogonality.

Proof that orthogonality implies closest point:

Conversely, suppose p ∈ S satisfies (b - p) ⊥ S. We want to show p is the closest point to b in S.

Take any other point q ∈ S. Then p - q ∈ S (since S is a subspace), so (b - p) ⊥ (p - q).

By the Pythagorean theorem applied to the right triangle with legs (b - p) and (p - q):

||b - q||² = ||(b - p) + (p - q)||² = ||b - p||² + ||p - q||²

Since ||p - q||² ≥ 0, we have:

||b - q||² ≥ ||b - p||²

with equality if and only if q = p. Thus p is the unique closest point.

The key insight: Finding the projection is equivalent to finding a vector in S such that the error is orthogonal to S. This transforms a minimization problem into a system of linear equations.

The projection formula simplifies dramatically when the subspace has an orthonormal basis. If u₁, u₂, ..., uₖ are orthonormal vectors (mutually perpendicular unit vectors) spanning S, the projection becomes:

proj_S(b) = (u₁·b)u₁ + (u₂·b)u₂ + ... + (uₖ·b)uₖ = Σᵢ (uᵢᵀb)uᵢ

No matrix inversion required! This is because for orthonormal columns, AᵀA = I (the identity matrix).

Why does this work?

Let Q = [u₁ | u₂ | ... | uₖ]. Since the columns are orthonormal:

QᵀQ = I (the k×k identity matrix)

The general projection formula gives:

proj_S(b) = Q(QᵀQ)⁻¹Qᵀb = QI⁻¹Qᵀb = QQᵀb

Expanding QQᵀb:

QQᵀb = [u₁ | ... | uₖ] · [u₁ᵀb, ..., uₖᵀb]ᵀ = Σᵢ (uᵢᵀb)uᵢ

Each term (uᵢᵀb)uᵢ is the projection of b onto the line spanned by uᵢ, and the total projection is simply the sum of these individual projections.

Connection to Fourier Series:

The orthonormal projection formula is the discrete analog of Fourier series. In Fourier analysis, a function is decomposed as:

f(x) = Σₙ cₙ φₙ(x)

where {φₙ} are orthonormal basis functions (sines and cosines), and the coefficients are:

cₙ = ⟨f, φₙ⟩ = ∫ f(x)φₙ(x) dx

This is exactly the continuous analog of cᵢ = uᵢᵀb. Projection onto orthonormal bases is the fundamental operation behind:

• Discrete Fourier Transform (DFT): Projects signals onto complex exponential basis
• Wavelet Transform: Projects onto wavelet basis functions
• Principal Component Analysis: Projects onto eigenvectors of the covariance matrix
• Spherical Harmonics: Projects functions on the sphere onto harmonic basis

For any subspace S of a vector space V, the orthogonal complement S⊥ (read "S perp") is the set of all vectors orthogonal to every vector in S:

S⊥ = {v ∈ V : v · s = 0 for all s ∈ S}

The orthogonal complement is itself a subspace, and together S and S⊥ span the entire space:

V = S ⊕ S⊥ (direct sum decomposition)

This means every vector b ∈ V can be uniquely written as:

b = p + e where p ∈ S and e ∈ S⊥

The projection operation is precisely the operation that extracts the S component: proj_S(b) = p, while the complement projection extracts the S⊥ component: proj_{S⊥}(b) = e = b - p.

Connection to the Four Fundamental Subspaces:

For an m × n matrix A, there are four fundamental subspaces, related by orthogonal complements:

1. Column space of A: Col(A) ⊆ ℝᵐ (dimension = rank(A) = r)
2. Left null space of A: Null(Aᵀ) ⊆ ℝᵐ (dimension = m - r)
3. Row space of A: Row(A) = Col(Aᵀ) ⊆ ℝⁿ (dimension = r)
4. Null space of A: Null(A) ⊆ ℝⁿ (dimension = n - r)

The crucial orthogonality relationships:

• Col(A) ⊥ Null(Aᵀ): Column space and left null space are orthogonal complements in ℝᵐ
• Row(A) ⊥ Null(A): Row space and null space are orthogonal complements in ℝⁿ

When we project b onto Col(A), the error e = b - Ax̂ lands in Null(Aᵀ), which is precisely why Aᵀe = 0 (the normal equations).

We've stated repeatedly that orthogonal projection finds the closest point. Let's prove this rigorously from a purely algebraic perspective, connecting to the optimization viewpoint central to machine learning.

Theorem: Let S be a subspace of ℝⁿ and b ∈ ℝⁿ. Among all vectors s ∈ S, the orthogonal projection proj_S(b) uniquely minimizes ||b - s||.

Proof using calculus:

Let S = Col(A) where A is m × k with full column rank. We seek x ∈ ℝᵏ minimizing:

f(x) = ||b - Ax||² = (b - Ax)ᵀ(b - Ax)

Expanding:

f(x) = bᵀb - 2xᵀAᵀb + xᵀAᵀAx

Taking the gradient with respect to x:

∇f(x) = -2Aᵀb + 2AᵀAx

Setting the gradient to zero:

AᵀAx = Aᵀb

These are the normal equations. Since AᵀA is positive definite (when A has full column rank), the Hessian ∇²f = 2AᵀA is positive definite, confirming this is a minimum.

The unique solution is x̂ = (AᵀA)⁻¹Aᵀb, giving projection p = Ax̂ = A(AᵀA)⁻¹Aᵀb.

Geometric proof (without calculus):

Let p = proj_S(b) and let q be any other point in S. We want to show ||b - p|| < ||b - q||.

Define e = b - p (the error). By the orthogonality principle, e ⊥ S.

Since both p and q are in S, the vector (p - q) ∈ S, so e ⊥ (p - q).

Now compute: ||b - q||² = ||(b - p) + (p - q)||² = ||e + (p - q)||² = ||e||² + ||p - q||² + 2e·(p - q) [expansion] = ||e||² + ||p - q||² + 0 [orthogonality] = ||b - p||² + ||p - q||²

Since ||p - q||² ≥ 0, we have:

||b - q||² ≥ ||b - p||²

Equality holds if and only if ||p - q|| = 0, i.e., q = p.

This proves p is the unique closest point—the distance is strictly larger for any other point in S.