Singular Value Decomposition

The Fundamental SVD Equation

Every real $m \times n$ matrix $A$ can be factored as:

A = U * Sigma * V^T

  Matrix A (m × n)          Left Vectors U (m × m)    Singular Values Σ (m × n)   Right Vectors V^T (n × n)
  ┌──────────────┐          ┌──────────────┐          ┌───┬───┬───┐               ┌──────────────┐
  │              │    =     │              │    ×     │σ1 │ 0 │ 0 │       ×       │              │
  │              │          │              │          ├───┼───┼───┤               │              │
  └──────────────┘          └──────────────┘          └───┴───┴───┘               └──────────────┘

1. Left-Singular Vectors U (m × m): Orthogonal matrix ($U^T U = I$). Columns are eigenvectors of $A A^T$.
2. Singular Values Sigma (m × n): Diagonal matrix. Values $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$ are square roots of eigenvalues of $A^T A$.
3. Right-Singular Vectors V^T (n × n): Orthogonal matrix ($V^T V = I$). Columns of $V$ are eigenvectors of $A^T A$.

Geometric Interpretation: Three Transformations

SVD breaks down any linear transformation into three geometric steps:

1. V^T: Rotate the input vector space.
2. Sigma: Scale along orthogonal axes by singular values $\sigma_i$.
3. U: Rotate into the output vector space.

  Unit Circle x ──► [ Rotate V^T ] ──► [ Stretch Σ by σ1, σ2 ] ──► [ Rotate U ] ──► Ellipse Ax

Truncated SVD & Image Compression

To compress a matrix $A$ to rank $k \ll \min(m, n)$:

Keep only the top $k$ largest singular values:

A_k = sum_{i=1}^k \sigma_i u_i v_i^T

The Eckart-Young-Mirsky Theorem proves that $A_k$ is the mathematically optimal rank-$k$ approximation of $A$, minimizing Frobenius norm error $\|A - A_k\|_F$.

Key Machine Learning Applications

1. Principal Component Analysis (PCA): Compute SVD on mean-centered matrix $X$. The right-singular vectors $V$ are the principal components.
2. Latent Semantic Analysis (LSA): Apply SVD to term-document matrices to discover hidden semantic concepts in text collections.
3. Recommender Systems: Decompose sparse rating matrices for collaborative filtering.

Say this out loud

SVD factorizes any matrix A into U Sigma V^T, where U and V are orthogonal rotation matrices and Sigma contains non-negative singular values. Truncated SVD keeps the top k singular values to give the optimal low-rank matrix approximation under the Eckart-Young theorem. SVD forms the mathematical engine behind PCA, dimensional reduction, and latent semantic analysis.

Follow-ups to expect

• What is the computational complexity of full SVD on an m × n matrix? Full SVD takes O(m n^2 + n^3) time. For large matrices, randomized SVD algorithms approximate singular vectors in O(m n k) time.
• What happens if matrix A is symmetric and positive semi-definite? SVD becomes identical to Eigendecomposition: U = V, and singular values equal eigenvalues.