Least Squares, Projections, Eigenvalues & SVD

When you have 1,000 data points and a 2-parameter line y = mx + c, you cannot pass a straight line through every point.

Least Squares provides the optimal compromise:

min_(x) L(x) = \|Ax - b\|² = (Ax - b)^T (Ax - b)

Squaring each error penalizes large outliers more heavily and makes the objective function smooth, convex, and differentiable with a single unique global minimum.

In Ordinary Least Squares (OLS) Linear Regression in Econometrics and Data Science, least squares fits trendlines across GDP, inflation, and employment indicators to forecast market trends.

Carl Friedrich Gauss claimed to have used least squares since 1795 to recover Ceres, publishing the method in 1809 and proving the Gauss-Markov theorem (OLS is the Best Linear Unbiased Estimator).

Mnemonic: "Minimize the Sum of Squared Gaps."

min \|Ax - b\|²: The global standard for optimal data fitting.

When A is an m × n tall matrix (m > n), Ax = b cannot be solved.

Multiply both sides by A^T:

A^T A x̂ = A^T b

Look at what happened to the dimensions:

• A^T A is now a square n × n matrix!
• A^T b is an n × 1 vector.

If the columns of A are linearly independent, A^T A is guaranteed to be symmetric, positive-definite, and invertible! Inverting it gives the closed-form solution x̂ = (A^T A)^(-1) A^T b.

In Geodetic Surveying and GPS Satellites, Normal Equations solve for receiver position (x, y, z) from dozens of simultaneous noisy pseudorange satellite pings.

Carl Friedrich Gauss formulated the Normal Equations in 1809 in Theoria Motus Corporum Coelestium, developing Gaussian elimination to solve the A^T A system efficiently.

The Magic Transformation: "Multiply by A^T."

Ax = b ⟶ A^T A x̂ = A^T b. Makes rectangular systems square and solvable!

The projection matrix P = A(A^T A)^(-1)A^T is a mathematical machine: drop any vector b into it, and it outputs the shadow b̂ = Pb lying in C(A).

It has two defining properties:

1. Symmetric (P^T = P): The projection is orthogonal (90^∘), not oblique.
2. Idempotent (P² = P): Projecting a vector that is already on the floor changes nothing. Dropping a shadow twice is the same as dropping it once.

The complementary matrix I - P projects onto the orthogonal null space, extracting the residual e = (I - P)b.

In Statistical ANOVA and Linear Hypothesis Testing, projection hat matrices H = X(X^T X)^(-1)X^T decompose total variance into explained sum of squares and residual sum of squares.

Alston Scott Householder in 1958 developed orthogonal projection matrices and elementary reflectors to stabilize numerical computations in matrix factorizations.

Properties of Projection:

• P² = P (Idempotent: once you're on the floor, you stay on the floor).
• P^T = P (Symmetric: orthogonal drop).

An educational mathematical repair diagram on refined warm ivory paper (#fdf8ee) with a subtle hairline frame (#e8e2d5).

Top section: Title with decorative tildes: "~ The Pseudoinverse: Resolving the Rank-Deficiency Condition ~". Subtitle in italic serif: "Correcting the precondition: why (A^T A)^(-1) fails when columns are collinear."

Middle section: A two-case analytical comparison:

Case 1 (Full Column Rank, rank r = n): A^T A is non-singular and invertible ⟹ Left inverse formula A^+ = (A^T A)^(-1) A^T is valid.

Case 2 (Rank-Deficient, rank r < n): Columns of A are linearly dependent ⟹ A^T A has zero eigenvalues (det(A^T A) = 0); inverting (A^T A) is mathematically impossible!

Draw a red cancellation line through (A^T A)^(-1) for rank-deficient matrices.

Show the universal SVD solution: "A^+ = V Σ^+ U^T where Σ^+ = diag(1/σ₁, ..., 1/σ_r, 0, ..., 0)".

Bottom section: Card: "The SVD formulation of A^+ is the ONLY definition that holds universally for all matrices, regardless of rank deficiency or dimension."

Clean box layout, high contrast warning badges, generous whitespace.

This principle is foundational across deep learning optimization, high-dimensional representation, and modern LLM architectures.

"[Repair] SVD Pseudoinverse for Rank-Deficient Systems (Fixing Slide 46): Invariance and structure determine stability under spatial and numerical transformations."

Take a unit square of area 1 in 2D and apply matrix transformation A. The square stretches into a parallelogram.

What is the area of that new parallelogram? Exactly |det(A)|!

In 3D, it measures how the unit cube's volume scales.

• If det(A) = 2, space expands by 2×.
• If det(A) = 0, the square is flattened onto a 1D line (area = 0). Dimensional collapse has occurred, meaning A cannot be inverted!
• If det(A) < 0, space was flipped inside out (like looking in a mirror).

In Multivariable Integration (Jacobian Change of Variables ∬ f(x, y) dx dy = ∬ f(u, v) |det(J)| du dv) and Computer Graphics Collision Detection, determinants track volume compression in physical simulations.

Gottfried Wilhelm Leibniz used determinants in 1693 to solve linear systems, but Augustin-Louis Cauchy in 1812 established modern determinant notation and proved det(AB) = det(A)det(B).

Geometric Hook: "Determinant = Volume Multiplier."

If det(A) = 0, volume was squashed to zero ⟹ No inverse exists.

The Trace of an n × n matrix is computed simply by adding its main diagonal entries: tr(A) = A_(11) + A_(22) + ṡ + A_(nn).

Despite its trivial arithmetic, it holds deep algebraic magic:

1. It equals the exact sum of all eigenvalues: ∑ A_(ii) = ∑ λᵢ.
2. It satisfies cyclic invariance: tr(AB) = tr(BA).
3. If you rotate or tilt your coordinate axes (P A P^(-1)), individual matrix entries change wildly, but the trace never changes! It is an intrinsic invariant of the linear operator.

In Quantum Mechanics and Density Matrix Theory, the trace of a quantum density operator tr(ρ) = 1 enforces total probability conservation, and tr(ρ A) calculates the quantum expectation value of observable A.

Arthur Cayley and Ferdinand Georg Frobenius in the 19th century identified the trace and determinant as the fundamental coefficients of a matrix's characteristic polynomial det(λ I - A).

Identity Hook: "Trace = Sum of Diagonal = Sum of Eigenvalues."

Cyclic property: You can cycle the matrices inside a trace: tr(ABC) = tr(CAB).

Most vectors change both their length and direction when transformed by a matrix A.

However, certain special vectors do not change direction!

Applying A to these special vectors merely stretches or shrinks them by a factor λ:

Av = λ v

These invariant directions are eigenvectors v, and the scaling multipliers are eigenvalues λ.

Rewriting as (A - λ I)v = 0 shows that v sits in the null space of (A - λ I). For a non-trivial null space to exist, the determinant must vanish: det(A - λ I) = 0.

In Google's Original PageRank Algorithm, web pages are ranked by calculating the principal eigenvector of the web hyperlink stochastic transition matrix (Pr = 1 · r).

Leonhard Euler studied principal axes of rotation in 1765, and David Hilbert coined the German term Eigenwert ("own value" / "characteristic value") in 1904.

Visual Law: "Directions That Don't Rotate."

Av = λ v. The matrix A acts on v like a simple number λ.

The roots of the characteristic polynomial det(A - λ I) = 0 are the eigenvalues λ₁, ṡ, λₙ.

They act as the vital diagnostic numbers of the matrix:

• λ > 1: Space stretches (divergent growth).
• 0 < λ < 1: Space contracts (decay / settling).
• λ < 0: Space flips direction (oscillation).
• λ = 0: Space is flattened to zero (rank loss / singular matrix).
• Complex λ = a ± bi: Pure spatial rotation with spiraling growth.

In Bridge and Structural Engineering (such as the Tacoma Narrows Bridge analysis), mechanical engineers compute eigenvalues of structural stiffness matrices; if an external wind frequency matches an eigenvalue, resonance causes catastrophic collapse.

Augustin-Louis Cauchy in 1829 proved that all eigenvalues of a real symmetric matrix are strictly real numbers, unlocking the foundation of spectral mechanics.

Stability Rule:

• |λ| > 1: Explodes to ∞.
• |λ| < 1: Decays to 0 (Stable).
• |λ| = 1: Perpetual oscillation.

Once you find eigenvalue λ, substitute it into (A - λ I)v = 0 and solve for the null space. The non-zero vectors in this null space are the eigenvectors.

If an n × n matrix has n independent eigenvectors, collect them into matrix V = [v₁ ṡ vₙ].

In this new eigenvector basis, matrix A becomes a simple diagonal matrix Λ:

A = V Λ V^(-1)

In this custom basis, variables do not interact; each coordinate xᵢ simply multiplies by λᵢ.

In Facial Recognition (Eigenfaces in Computer Vision), eigenvectors of the face covariance matrix capture the principal visual features (lighting, eye distance, jaw shape) across facial databases.

Karl Pearson in 1901 and Harold Hotelling in 1933 used eigenvectors to invent Principal Component Analysis (PCA) to find the lines of closest fit to multi-dimensional data clouds.

Mnemonic: "Eigenvectors are the Natural Axes."

Line your coordinate system up with the eigenvectors, and the matrix becomes diagonal!

The Spectral Theorem is the pinnacle of linear algebra: every real symmetric matrix A = A^T can be factored into A = Q Λ Q^T, where Q is an orthogonal matrix of eigenvectors (Q^T = Q^(-1)).

Written as outer products:

A = λ₁ q₁ q₁^T + λ₂ q₂ q₂^T + ṡ + λₙ qₙ qₙ^T

Each term qᵢ qᵢ^T is a rank-1 projection matrix onto eigenvector qᵢ.

Just as an optical prism splits white light into distinct pure wavelengths, the spectral theorem splits a complex matrix into independent orthogonal geometric slices weighted by λᵢ.

In Graph Neural Networks (Spectral GNNs) and Spectral Clustering, the Graph Laplacian matrix L = D - W is decomposed spectrally to perform graph convolution and partition social networks into communities.

David Hilbert in 1904 generalized Cauchy's matrix spectral theorem to infinite-dimensional Hilbert spaces, laying the mathematical foundation for Werner Heisenberg and Erwin Schrödinger's quantum wave mechanics.

Formula: "A = Q Λ Q^T = ∑ λᵢ qᵢ qᵢ^T."

Sum of orthogonal projections weighted by their eigenvalues.

Spectral decomposition requires square, symmetric matrices. What if A is an m × n rectangular dataset?

SVD works on every single matrix that exists. It proves that any linear transformation can be decomposed into three simple geometric steps:

1. V^T: Rotate the input space using orthonormal basis V.
2. Σ: Scale each coordinate by singular value σᵢ (and change dimension from n to m).
3. U: Rotate the output space using orthonormal basis U.

Circles always get transformed into ellipses; SVD identifies the axes of that ellipse.

In Recommendation Systems (Netflix Prize / Collaborative Filtering), SVD factorizes massive user-movie rating matrices to discover latent genre preferences and predict ratings for unseen films.

Eugenio Beltrami (1873) and Camille Jordan (1874) independently discovered SVD, which was finalized in modern form by Carl Eckart and Gale Young in 1936 for low-rank matrix approximation.

Three Steps of SVD: "Rotate → Stretch → Rotate."

A = U Σ V^T. Orthonormal in, diagonal stretch, orthonormal out.

When a matrix A acts on a sphere of unit radius \|x\| = 1, the sphere is warped into an m-dimensional hyper-ellipse.

The half-lengths of the principal axes of this ellipse are precisely the singular values σ₁, σ₂, ṡ, σ_r.

Because they represent physical lengths of geometric axes, they can never be negative: σᵢ ≥ 0.

The largest singular value σ₁ is the matrix's maximum amplification factor (its spectral norm \|A\|₂).

In Numerical Condition Number Analysis (c = σ₁ / σₙ), software tools measure whether a matrix is ill-conditioned: if c > 10^(15), solving Ax = b will suffer from catastrophic floating-point cancellation.

Henri Poincaré and Émile Picard in the 1890s used singular values in integral equations, connecting them to variational maximum-gain problems.

Geometric Fact: "Singular Values are the Ellipse Radii."

Sorted from biggest to smallest: σ₁ ≥ σ₂ ≥ ṡ ≥ 0. They measure axis stretch.

How do you compress a 10-megapixel image or a 100,000-column data table?

Write the full SVD as a sum of rank-1 matrices:

A = σ₁ u₁ v₁^T + σ₂ u₂ v₂^T + ṡ + σ_r u_r v_r^T

The Eckart-Young-Mirsky Theorem proves a miraculous result: if you keep only the top k terms (k ≪ r) and discard the rest, you get Aₖ, the provably best rank-k approximation of A possible in mathematics!

The approximation error is simply the sum of discarded singular values: \|A - Aₖ\|_F² = ∑_(j=k+1)^r σⱼ².

In Image Compression and Latent Semantic Analysis (LSA in NLP), storing k(uᵢ + vᵢ) requires a tiny fraction of the memory of storing the full matrix A, enabling massive data reduction.

Carl Eckart and Gale Young in 1936 published this theorem in Psychometrika, revolutionizing data reduction across statistics, psychology, and signal processing.

Rule: "Keep the Big σ's, Drop the Small Ones."

Rank-k truncated SVD retains the most signal with the fewest numbers.

Suppose you have a 100-dimensional data cloud. How do you visualize it in 2D?

1. Center: Subtract the mean vector μ so the data is centered at the origin.
2. Covariance: Compute sample covariance S = 1/n X^T X.
3. Eigendecompose: Find eigenvectors of S: Swᵢ = λᵢ wᵢ.

The first eigenvector w₁ (with largest eigenvalue λ₁) points in the direction where data spreads out the most (maximum variance). The second eigenvector points in the orthogonal direction of next-highest variance. Projecting data onto (w₁, w₂) reveals the 2D skeleton of the high-dimensional data.

In Single-Cell RNA Sequencing (Genomics), biologists reduce 20,000 gene expression dimensions to 2 principal components to visually cluster and discover new cell types.

Karl Pearson invented PCA in 1901 as an analogue of the principal axis theorem in classical mechanics, later expanded independently by Harold Hotelling in 1933.

Mnemonic: "Center, Covariance, Eigendecompose."

First principal component = Direction of widest spread.