Singular Value Decomposition (SVD)

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Statement of the SVD
6. Existence Proof
7. Geometric Interpretation
8. Outer Product and Rank Structure
9. Relationship to Eigendecomposition
10. The Eckart-Young-Mirsky Theorem
11. Truncated SVD and PCA
12. The Moore-Penrose Pseudoinverse
13. Application: Low-Rank Adaptation (LoRA)
14. Application: Matrix Completion
15. Common Pitfalls and Misconceptions
16. Research Perspective
17. Summary of Takeaways
18. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. State the SVD theorem and prove existence using the spectral theorem on $\mathbf{A}^T\mathbf{A}$.
2. Interpret singular values as axis lengths of the transformation ellipsoid.
3. Prove the Eckart-Young theorem for optimal rank-$k$ approximation in the Frobenius norm.
4. Connect SVD of a centered data matrix to PCA and covariance eigendecomposition.
5. Define the Moore-Penrose pseudoinverse and solve least-squares problems via SVD.
6. Explain why low-rank factorization (LoRA, matrix completion) is justified by singular value decay.

Prerequisites

• Eigenvalues & Eigenvectors: spectral theorem, positive semidefinite matrices, Rayleigh quotient.
• Matrix Operations & Linear Transformations: rank, four subspaces, Frobenius norm.

Notation

• $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$ — SVD with $\mathbf{U}, \mathbf{V}$ orthogonal
• $\sigma_1 \geq \cdots \geq \sigma_r$ — Singular values, $r = \text{rank}(\mathbf{A})$
• **$\** — \mathbf{A}\ — _F, \ — \mathbf{A}\ — _2$ — Frobenius and spectral norms
• $\mathbf{A}_k$ — Rank-$k$ truncated SVD approximation
• $\mathbf{A}^+$ — Moore–Penrose pseudoinverse

Core Intuition

Eigendecomposition applies only to square matrices and requires diagonalizability. The Singular Value Decomposition (SVD) applies to every matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ and always exists with orthogonal factors. It reveals that any linear map is a rotation, axis-aligned scaling, and another rotation:

The singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq 0$ measure the "strength" of each rank-1 component. Truncating small singular values yields the best low-rank approximation — the mathematical justification for PCA, compression, LoRA fine-tuning, and collaborative filtering.

Series context. This is Part IV of Chapter 1. It completes the linear algebra foundation before Positive Definite Matrices.

Statement of the SVD

Theorem 1 (Singular Value Decomposition). For every matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ with rank $r$, there exist:

• Orthogonal $\mathbf{U} \in \mathbb{R}^{m \times m}$ (left singular vectors)
• Orthogonal $\mathbf{V} \in \mathbb{R}^{n \times n}$ (right singular vectors)
• Diagonal $\boldsymbol{\Sigma} \in \mathbb{R}^{m \times n}$ with $\Sigma_{ii} = \sigma_i > 0$ for $i = 1, \ldots, r$ and $\Sigma_{ii} = 0$ otherwise, where $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r$

such that

The $\sigma_i$ are the singular values; columns $\mathbf{u}_i$ of $\mathbf{U}$ and $\mathbf{v}_i$ of $\mathbf{V}$ are left and right singular vectors respectively.

Compact SVD. Often written with $\mathbf{U}_r \in \mathbb{R}^{m \times r}$, $\boldsymbol{\Sigma}_r = \text{diag}(\sigma_1, \ldots, \sigma_r)$, $\mathbf{V}_r \in \mathbb{R}^{n \times r}$:

Existence Proof

Proof. The matrix $\mathbf{A}^T\mathbf{A} \in \mathbb{R}^{n \times n}$ is symmetric and positive semidefinite, since

By the spectral theorem:

where $\mathbf{V}$ is orthogonal and $\boldsymbol{\Lambda} = \text{diag}(\lambda_1, \ldots, \lambda_n)$.

Step 1 — Singular values. Define $\sigma_i = \sqrt{\lambda_i}$ for $i = 1, \ldots, r$ where $r = \text{rank}(\mathbf{A}) = \text{rank}(\mathbf{A}^T\mathbf{A})$.

Step 2 — Left singular vectors. For $i = 1, \ldots, r$, define

This is well-defined since $\sigma_i > 0$ for $i \leq r$. Verify orthonormality:

Step 3 — Extension. Extend $\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$ to an orthonormal basis of $\mathbb{R}^m$ (adding vectors in $\text{null}(\mathbf{A}^T)$ if $r < m$).

Step 4 — Verification. For $i \leq r$: $\mathbf{A}\mathbf{v}_i = \sigma_i \mathbf{u}_i$ by (5). For $i > r$: $\lambda_i = 0$, so $\|\mathbf{A}\mathbf{v}_i\|^2 = \mathbf{v}_i^T\mathbf{A}^T\mathbf{A}\mathbf{v}_i = 0$, hence $\mathbf{A}\mathbf{v}_i = \mathbf{0}$.

In matrix form: $\mathbf{A}\mathbf{V} = \mathbf{U}\boldsymbol{\Sigma}$, so $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$. $\blacksquare$

Important equation. Equation (1) always exists — no diagonalizability requirement. This universality makes SVD the default tool for rectangular data matrices.

Geometric Interpretation

The map $\mathbf{x} \mapsto \mathbf{A}\mathbf{x}$ decomposes as:

The unit sphere $\{\mathbf{x} : \|\mathbf{x}\| = 1\}$ maps to an ellipsoid in $\mathbb{R}^m$ with semi-axis lengths $\sigma_i$ along directions $\mathbf{u}_i$.

Visual description. Picture inflating a balloon (sphere) through a pipe (linear map). The balloon emerges as an ellipsoid. The SVD identifies the balloon's original orientation ($\mathbf{V}$), how much it stretched along each axis ($\boldsymbol{\Sigma}$), and the final orientation in output space ($\mathbf{U}$).

Relation to four subspaces:

• $\text{col}(\mathbf{A}) = \text{span}(\mathbf{u}_1, \ldots, \mathbf{u}_r)$
• $\text{row}(\mathbf{A}) = \text{span}(\mathbf{v}_1, \ldots, \mathbf{v}_r)$
• $\text{null}(\mathbf{A}) = \text{span}(\mathbf{v}_{r+1}, \ldots, \mathbf{v}_n)$
• $\text{null}(\mathbf{A}^T) = \text{span}(\mathbf{u}_{r+1}, \ldots, \mathbf{u}_m)$

Outer Product and Rank Structure

Theorem 2 (Outer Product Expansion).

Each term $\sigma_i \mathbf{u}_i \mathbf{v}_i^T$ is a rank-1 matrix. The SVD decomposes $\mathbf{A}$ into $r$ rank-1 components ordered by magnitude $\sigma_i$.

Proof. $(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T) = \sum_i \sigma_i \mathbf{u}_i \mathbf{v}_i^T$ by matrix multiplication. $\blacksquare$

This connects to the outer-product view of matrix multiplication from Matrix Operations.

Relationship to Eigendecomposition

For $\mathbf{A} \in \mathbb{R}^{m \times n}$:

Right singular vectors are eigenvectors of $\mathbf{A}^T\mathbf{A}$; left singular vectors are eigenvectors of $\mathbf{A}\mathbf{A}^T$; singular values are common square roots of eigenvalues.

When $\mathbf{A}$ is symmetric: SVD coincides with spectral decomposition (up to sign flips of $\mathbf{u}_i = \mathbf{v}_i$).

Hierarchy of factorizations:

The Eckart-Young-Mirsky Theorem

Definition 1 (Frobenius norm). $\|\mathbf{A}\|_F = \sqrt{\sum_{i,j} A_{ij}^2} = \sqrt{\sum_{i=1}^r \sigma_i^2}$.

Definition 2 (Spectral norm). $\|\mathbf{A}\|_2 = \sigma_1$ (largest singular value).

Theorem 3 (Eckart-Young-Mirsky). The best rank-$k$ approximation to $\mathbf{A}$ in Frobenius norm is

with error

Proof (Frobenius norm — key steps). Let $\mathbf{B}$ be any rank-$k$ matrix. Then $\dim(\text{null}(\mathbf{B})) \geq n - k$. The space $\text{span}(\mathbf{v}_1, \ldots, \mathbf{v}_{k+1})$ has dimension $k+1$, so there exists unit $\mathbf{z}$ in both null spaces. Then:

since $\mathbf{z}$ has a component along $\mathbf{v}_{k+1}$. Hence $\|\mathbf{A} - \mathbf{B}\|_F \geq \sigma_{k+1}$. The truncated SVD achieves equality. $\blacksquare$

Energy captured:

Important equation. Equation (15) quantifies how much of a matrix's structure is captured by its top-$k$ singular components — the basis for dimensionality reduction and LoRA.

Truncated SVD and PCA

For centered data $\mathbf{X} \in \mathbb{R}^{N \times d}$ (rows = samples):

Sample covariance:

Hence:

• Principal components = columns of $\mathbf{V}$
• Covariance eigenvalues = $\sigma_i^2 / (N-1)$
• PC scores = $\mathbf{X}\mathbf{V} = \mathbf{U}\boldsymbol{\Sigma}$

Numerical advantage. SVD of $\mathbf{X}$ avoids forming $\mathbf{X}^T\mathbf{X}$, which squares the condition number. Always prefer SVD over direct covariance eigendecomposition for ill-conditioned data.

The Moore-Penrose Pseudoinverse

Definition 3. The pseudoinverse $\mathbf{A}^+ \in \mathbb{R}^{n \times m}$ is:

where $\boldsymbol{\Sigma}_r^{-1} = \text{diag}(1/\sigma_1, \ldots, 1/\sigma_r)$.

Theorem 4. The minimum-norm least-squares solution to $\mathbf{A}\mathbf{x} = \mathbf{b}$ is $\hat{\mathbf{x}} = \mathbf{A}^+\mathbf{b}$.

Proof sketch. $\mathbf{A}^+\mathbf{b}$ lies in $\text{row}(\mathbf{A})$ and satisfies the normal equations. Minimum norm among all least-squares solutions follows from orthogonality to $\text{null}(\mathbf{A})$. $\blacksquare$

When $\mathbf{A}$ has full column rank, $\mathbf{A}^+ = (\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^T$ — the familiar form from Matrix Operations.

Application: Low-Rank Adaptation (LoRA)

Fine-tuning a pretrained weight matrix $\mathbf{W}_0 \in \mathbb{R}^{d \times d}$ uses:

SVD justification. If the ideal update $\Delta\mathbf{W}^*$ has singular values decaying rapidly, then by Eckart-Young:

with equality when $\mathbf{B}\mathbf{A} = (\Delta\mathbf{W}^*)_r$. Low-rank adaptation is optimal when task-specific changes are approximately low-rank.

Parameter count. Full update: $d^2$. LoRA: $2dr$. For $d = 4096$, $r = 16$: reduction factor $d/(2r) = 128$.

Application: Matrix Completion

In collaborative filtering, the rating matrix $\mathbf{R} \in \mathbb{R}^{m \times n}$ has entries observed only on a subset $\Omega$. The low-rank hypothesis: $\mathbf{R} \approx \mathbf{U}\mathbf{V}^T$ with $\mathbf{U} \in \mathbb{R}^{m \times k}$, $\mathbf{V} \in \mathbb{R}^{n \times k}$.

Regularized objective:

This is a partial, regularized low-rank factorization. When all entries are observed, the optimum relates to the truncated SVD of $\mathbf{R}$.

Common Pitfalls and Misconceptions

Pitfall 1: Confusing SVD with eigendecomposition of $\mathbf{A}$. For nonsquare or nonsymmetric $\mathbf{A}$, eigenvalues of $\mathbf{A}$ may be complex or fail to diagonalize. SVD always uses orthogonal factors and real nonnegative singular values.

Pitfall 2: Truncating SVD without checking decay. If singular values decay slowly, rank-$k$ truncation loses substantial information. Inspect the scree plot ($\sigma_i$ vs $i$).

Pitfall 3: Applying PCA via SVD without centering. SVD of raw $\mathbf{X}$ finds directions of maximum variance including the mean offset. Always center columns first.

Pitfall 4: Assuming LoRA rank $r$ is universally sufficient. Optimal $r$ depends on task complexity and how quickly $\Delta\mathbf{W}^*$ singular values decay.

Pitfall 5: Using full SVD for very large matrices. Randomized SVD methods approximate top-$k$ components in $O(mn \log k)$ rather than $O(\min(mn^2, m^2 n))$.

Research Perspective

The SVD was developed independently by Beltrami (1873), Jordan (1874), and later formalized by Eckart and Young (1936) for low-rank approximation. Golub and Reinsch (1970) provided the first stable numerical algorithm.

In machine learning, latent semantic indexing (Deerwester et al., 1990) applied truncated SVD to term-document matrices. Matrix completion (Candès & Recht, 2009; Netflix Prize) exploited low-rank structure with theoretical guarantees. LoRA (Hu et al., 2021) brought low-rank updates to billion-parameter language models, motivated by the empirical observation that fine-tuning changes are low-rank.

Randomized numerical linear algebra (Halko et al., 2011) enables approximate SVD at scale — essential for modern data pipelines.

Summary of Takeaways

• SVD — $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$ — Universal factorization
• Rank-$k$ approx — $\mathbf{A}_k = \mathbf{U}_k\boldsymbol{\Sigma}_k\mathbf{V}_k^T$ — PCA, compression
• Eckart-Young — Optimal in $\ — \cdot\ — _F$ — Justifies LoRA, truncation
• Pseudoinverse — $\mathbf{A}^+ = \mathbf{V}_r\boldsymbol{\Sigma}_r^{-1}\mathbf{U}_r^T$ — Least squares
• Energy ratio — $\sum_{i=1}^k \sigma_i^2 / \sum \sigma_i^2$ — Variance explained

Next article: Positive Definite Matrices → — covariance, convexity, and the geometry of optimization.

Exercises

Exercise 1. Compute the SVD of $\mathbf{A} = \begin{bmatrix} 3 & 0 \\ 0 & -2 \end{bmatrix}$. Identify $\mathbf{U}$, $\boldsymbol{\Sigma}$, $\mathbf{V}$ and verify (1).

Exercise 2. Prove $\|\mathbf{A}\|_F^2 = \sum_i \sigma_i^2$ and $\|\mathbf{A}\|_2 = \sigma_1$.

Exercise 3. For rank-1 $\mathbf{A} = \mathbf{u}\mathbf{v}^T$, show the SVD has a single singular value $\sigma_1 = \|\mathbf{u}\|\|\mathbf{v}\|$.

Exercise 4 (Eckart-Young). For $\mathbf{A}$ with $\sigma_1 = 5, \sigma_2 = 3, \sigma_3 = 1$, compute $\|\mathbf{A} - \mathbf{A}_1\|_F$ and the fraction of energy in the rank-1 approximation.

Exercise 5 (PCA). Given centered $\mathbf{X} \in \mathbb{R}^{100 \times 5}$ with SVD singular values $(10, 5, 2, 0.5, 0.1)$, compute the proportion of variance explained by the first two principal components.

Exercise 6 (Pseudoinverse). For $\mathbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$, compute the SVD and $\mathbf{A}^+$. Verify $\mathbf{A}\mathbf{A}^+\mathbf{A} = \mathbf{A}$.

Exercise 7 (Conceptual). Explain why $\mathbf{A}^T\mathbf{A}$ and $\mathbf{A}\mathbf{A}^T$ have the same nonzero eigenvalues, and relate them to singular values of $\mathbf{A}$.

Appendix: The Polar Decomposition

Every square matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ admits a polar decomposition:

where $\mathbf{Q}$ is orthogonal and $\mathbf{P} = (\mathbf{A}^T\mathbf{A})^{1/2}$ is symmetric positive semidefinite.

Derivation from SVD. Write $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$. Define $\mathbf{Q} = \mathbf{U}\mathbf{V}^T$ (orthogonal when $\mathbf{A}$ is square and full rank) and $\mathbf{P} = \mathbf{V}\boldsymbol{\Sigma}\mathbf{V}^T$ (symmetric PSD). Then $\mathbf{A} = \mathbf{Q}\mathbf{P}$.

Interpretation. $\mathbf{P}$ captures the "stretch" part of the transformation; $\mathbf{Q}$ captures the "rotation" part. For symmetric $\mathbf{A}$, the polar decomposition coincides with the spectral theorem ($\mathbf{Q} = \mathbf{I}$, $\mathbf{P} = \mathbf{A}$ when $\mathbf{A} \succ 0$).

Connection to optimization. The polar decomposition appears in orthogonality constraints on weight matrices (orthogonal regularization) and in analyzing the singular value thresholding operator used in matrix completion algorithms.