Projections & Least Squares Regression

The Geometry of Fitting

Most real world systems are overdetermined: we have more equations than unknowns. The system Ax = b has no exact solution. The data is too noisy, the model is too simple, or both.

Least Squares asks: "If we cannot hit b exactly, what is the closest we can get?" The answer is the projection of b onto the column space of A

The Core Insight

Linear regression, polynomial fitting, and even deep learning (in parts) all reduce to projections. The error is minimized when it is perpendicular to the subspace of possible outputs.

Vector Projection

Before matrices, let us project a single vector a onto another vector b

\text{proj}_{b}(a) = \frac{a \cdot b}{b \cdot b}b = \frac{a \cdot b}{\mid\mid b\mid\mid^{2}}b

The scalar \frac{a \cdot b}{b \cdot b} tells us how far along b the projection lands.

Vector Projection

Visualizing proj_b(a) and the orthogonal error vector.

Target Vector (a)

XY

Base Vector (b)

XY

Scalar Projection0.73

||a||

5.00

||proj||

3.73

||error||

3.33

The Projection

The component of a that lies along b This is what we keep.

The Error

e = a - \text{proj}_{b}(a) The residual, always perpendicular to b

Interactive: Fitting Lines

In coordinate space, "perpendicular error" translates to minimizing the sum of vertical distance squared. Drag the points to see how the optimal line shifts to keep the residuals orthogonal to the feature space.

Data Space

e ⊥ Column Space

Squares

Optimal Line

\hat{y} = 0.56x + 1.39

Orthogonality Check

The error vector e must be orthogonal to the feature space (Column Space of X).

e · 1 (Bias)

0.0000

e · x (Feature)

0.0000

Total Squared Error

4.41

Visualize this as the total area of all the squares in the plot. Least Squares finds the minimum possible area.

Column Space View

For a matrix A the column space C(A) is the set of all possible outputs Ax If b is not in C(A) we project it.

1. The target b lives in \mathbb{R}^{m} (m data points).
2. The column space C(A) is a subspace of \mathbb{R}^{m} (spanned by n features).
3. We find the point \hat{b} \in C(A) closest to b
4. The error e = b - \hat{b} is perpendicular to C(A)

Key Geometric Fact

The shortest distance from a point to a subspace is measured along the perpendicular. This is why A^{T}e = 0 (the error is orthogonal to every column of A

The Normal Equations

From the perpendicularity condition A^{T}(b - Ax) = 0 we simplify to find the best weights \hat{x}

A^{T}A\hat{x} = A^{T}b

Solution: \hat{x} = (A^{T}A)^{- 1}A^{T}b

When Does This Work?

The inverse (A^{T}A)^{- 1}(ATA)−1 exists only when $$A has full column rank, i.e., all columns are linearly independent. If features are collinear (one is a linear combination of others), A^{T}AATA is singular and cannot be inverted. This is exactly why ridge regression adds \lambda I to the diagonal: the matrix A^{T}A + \lambda I is always invertible for \lambda > 0 regardless of rank.

The Pseudoinverse

The matrix A^{+} = (A^{T}A)^{- 1}A^{T} is called the Moore Penrose Pseudoinverse. It gives the least squares solution even when A is not square.

Case Study: Bulb Lifespan Prediction

The Problem

You have 100 bulbs with features (voltage, temperature) and lifespan measurements. You want to fit a linear model: Lifespan = w₁×Voltage + w₂×Temperature + w₀.

The Setup

Design matrix A is 100×3 (100 samples, 3 features including bias). Target b is 100×1. We solve for w (3×1).

\hat{w} = (A^{T}A)^{- 1}A^{T}b

The Geometric View

The column space of A is a 3D subspace in 100D space. The vector b (lifespans) is projected onto this subspace. The residuals e = b - A\hat{w} are the prediction errors, perpendicular to all features.

QR Decomposition Solution

Directly computing (A^{T}A)^{- 1}(ATA)−1 is numerically unstable. In practice, we use QR decomposition.

1. Decompose A = QR where Q is orthogonal, R is upper triangular.
2. Substitute: (QR)^{T}(QR)\hat{x} = (QR)^{T}b(QR)T(QR)x^=(QR)Tb
3. Simplify: R^{T}Q^{T}QR\hat{x} = R^{T}Q^{T}b
4. Since Q^{T}Q = I R^{T}R\hat{x} = R^{T}Q^{T}b
5. Result: R\hat{x} = Q^{T}b (solve by back substitution)

Numerical Advantage: QR avoids squaring the condition number of A This is how numpy.linalg.lstsq works internally.

ML Applications

Linear Regression

The closed form solution w = (X^{T}X)^{- 1}X^{T}y is exactly the normal equations. Gradient descent converges to the same point.

Ridge Regression

Add regularization: w = (X^{T}X + \lambda I)^{- 1}X^{T}y When X^{T}X is singular (features are collinear), OLS breaks. Adding \lambda I shifts all eigenvalues away from zero, guaranteeing invertibility while also shrinking coefficients toward zero.

PCA via SVD

PCA finds the subspace that best approximates the data (least reconstruction error). This is a projection problem solved via SVD.

Kernel Methods

Kernel Ridge Regression projects data into a high dimensional feature space and applies least squares there (via the kernel trick).