Lesson 6.1: The Singular Value Decomposition (SVD)

The ultimate revelation of a matrix's geometry and the most powerful tool in linear algebra.

Welcome to what is arguably the most important, revealing, and powerful idea in all of linear algebra: the Singular Value Decomposition (SVD).

So far, we have learned about other ways to break down, or "factor," a matrix. Eigendecomposition (A=PDP−1A = PDP^{-1}) was incredible, but it had a major limitation: it only works for some square matrices.

But what about the rest of the universe? What about rectangular matrices, the kind that represent most real-world datasets (e.g., 1000 houses by 15 features)? How do we find the deep, geometric truth of these transformations?

The SVD is the answer. It works for every single matrix, with no exceptions. It provides a complete geometric understanding of any linear transformation.

The Big Idea: Any Transformation is a Rotation, a Stretch, and another Rotation

The Decomposition: A = UΣVᵀ
The SVD states that any linear transformation, no matter how complex it looks, can be broken down into three fundamental actions: a rotation, a simple scaling, and a final rotation.
A=UΣVTA = U\Sigma V^T
  • `V` (The Input Axes): An `n x n` Orthogonal Matrix. Its columns, {v1,v2,...}\{v_1, v_2, ...\}, are the right singular vectors. They form a perfect orthonormal basis for the input space. The `Vᵀ` in the formula performs the initial rotation.
  • `Σ` (The Scaling Factors): An `m x n` rectangular diagonal matrix. The values on its diagonal, σ1≥σ2≥...≥0\sigma_1 \ge \sigma_2 \ge ... \ge 0, are the singular values. This matrix does all the stretching and squashing.
  • `U` (The Output Axes): An `m x m` Orthogonal Matrix. Its columns, {u1,u2,...}\{u_1, u_2, ...\}, are the left singular vectors. They form a perfect orthonormal basis for the output space. `U` performs the final rotation.

The SVD finds the perfect input basis (`V`) and the perfect output basis (`U`) that make the transformation `A` become a simple diagonal scaling matrix `Σ`.

A Step-by-Step Geometric Journey

Visualizing y = Ax as y = UΣVᵀx
  1. Rotate the Input (`Vᵀx`): `Vᵀ` rotates your input vector `x` to align it with the new, ideal input axes defined by the columns of `V`.
  2. Scale the Components (`Σ(Vᵀx)`): `Σ` takes the rotated vector and simply stretches or squashes its components along the standard axes by the singular values `σᵢ`.
  3. Rotate to the Output (`U(ΣVᵀx)`): `U` takes the scaled vector and performs a final rotation to its position in the output space, aligned with the ideal output axes `uᵢ`.

SVD and the Four Fundamental Subspaces

The Ultimate Map of a Matrix
SVD provides orthonormal bases for all four fundamental subspaces simultaneously. For a matrix `A` of rank `r`:
  • Row Space `C(Aᵀ)`: Basis is the first `r` columns of `V`, {v1,...,vr}\{v_1, ..., v_r\}.
  • Null Space `N(A)`: Basis is the remaining `n-r` columns of `V`, {vr+1,...,vn}\{v_{r+1}, ..., v_n\}.
  • Column Space `C(A)`: Basis is the first `r` columns of `U`, {u1,...,ur}\{u_1, ..., u_r\}.
  • Left Null Space `N(Aᵀ)`: Basis is the remaining `m-r` columns of `U`, {ur+1,...,um}\{u_{r+1}, ..., u_m\}.

The core relationship:

Avi=σiui(for i=1,...,r)A v_i = \sigma_i u_i \quad (\text{for } i=1, ..., r)

How Do We Calculate It?

The Connection to Eigen-analysis
We find `U`, `Σ`, and `V` from the eigendecomposition of the symmetric matrices `AᵀA` and `AAᵀ`.
  1. Find `V` and `Σ` from `AᵀA`:
    • Construct the `n x n` symmetric matrix `AᵀA`.
    • Find its eigenvalues (`λᵢ`) and orthonormal eigenvectors.
    • The eigenvectors are the columns of `V`.
    • The singular values `σᵢ` are the square roots of the eigenvalues (σi=λi\sigma_i = \sqrt{\lambda_i}).
  2. Find `U`:
    • The eigenvectors of the `m x m` matrix `AAᵀ` are the columns of `U`.
    • Alternatively, and more quickly, use the formula ui=(1/σi)Aviu_i = (1/\sigma_i) A v_i for each `i`.
Summary: The Ultimate Revelation
    1. Universality: SVD works for any `m x n` matrix.
    2. The Geometry: Any transformation is a Rotate (`Vᵀ`) -> Stretch (`Σ`) -> Rotate (`U`).
    3. The Components:
      • `V`: Orthonormal basis for the input space (eigenvectors of `AᵀA`).
      • `Σ`: Diagonal matrix of singular values σi=λi\sigma_i = \sqrt{\lambda_i}.
      • `U`: Orthonormal basis for the output space.
    4. The Power: SVD provides a complete, orthonormal map of the Four Fundamental Subspaces.
Previous
Lesson 5.6: The QR Decomposition
Next
Lesson 6.2: Principal Component Analysis (PCA)