Singular Value Decomposition

⚡ Key Takeaways

Singular Value Decomposition (SVD) factors any real or complex matrix $A$ into $U\Sigma V^{*}$ , where $U$ and $V$ are orthogonal/unitary and $\Sigma$ is diagonal with nonnegative entries. Key result: every linear map is a rotation, followed by an axis-aligned stretch, followed by another rotation. Where it applies: dimensionality reduction, least squares, image compression, pseudoinverses, numerical rank. Who/when: roots in Beltrami (1873) and Jordan (1874); modern numerical algorithm by Golub–Kahan (1965).

💡 The Core Insight

Any linear transformation $A: \mathbb{R}^n \to \mathbb{R}^m$ can be decomposed into three geometric stages: rotate the input (via $V^{*}$ ), scale along orthogonal axes (via $\Sigma$ ), then rotate again into the output space (via $U$ ). The orthonormal vectors that get scaled cleanly — without shearing — are the singular vectors, and the scale factors are the singular values. This works even when eigenvectors fail to exist or fail to be orthogonal.

DefinitionSingular Value Decomposition

Let $A \in \mathbb{C}^{m\times n}$ (the real case $\mathbb{R}^{m\times n}$ is included). A singular value decomposition of $A$ is a factorization

1

\quad A = U\,\Sigma\,V^{*}

Derivation hint: this is the definition; existence is proven below via the spectral theorem applied to $A^{*}A$ . where:

$U \in \mathbb{C}^{m\times m}$ is unitary ( $U^{*}U = I_m$ ); its columns $u_1,\dots,u_m$ are the left singular vectors.
$V \in \mathbb{C}^{n\times n}$ is unitary ( $V^{*}V = I_n$ ); its columns $v_1,\dots,v_n$ are the right singular vectors.
$\Sigma \in \mathbb{R}^{m\times n}$ is a rectangular diagonal matrix with entries $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_p \ge 0$ on the diagonal, where $p = \min(m,n)$ . These are the singular values.
$V^{*}$ denotes the conjugate transpose of $V$ (just the transpose $V^{T}$ in the real case).

The number of nonzero singular values equals $\operatorname{rank}(A) = r$ . The defining relations connecting the three factors are

2

\quad A v_i = \sigma_i u_i, \qquad A^{*} u_i = \sigma_i v_i, \qquad i = 1,\dots,r

Derivation hint: read off column $i$ of $AV = U\Sigma$ and of $A^{*}U = V\Sigma^{T}$ .

DefinitionReduced (Thin) SVD

When $m > n$ , the bottom rows of $\Sigma$ are zero, and the last $m-n$ columns of $U$ contribute nothing. The thin SVD keeps only the first $r$ active components:

3

\quad A = U_r\,\Sigma_r\,V_r^{*} = \sum_{i=1}^{r} \sigma_i\, u_i v_i^{*}

Derivation hint: expand the matrix product $U\Sigma V^{*}$ column-by-column and discard terms multiplied by zero singular values. Here $U_r \in \mathbb{C}^{m\times r}$ , $\Sigma_r \in \mathbb{R}^{r\times r}$ is square diagonal with positive entries, and $V_r \in \mathbb{C}^{n\times r}$ . The rightmost form expresses $A$ as a sum of $r$ rank-one matrices.

TheoremExistence and Uniqueness

Every matrix $A \in \mathbb{C}^{m\times n}$ admits a singular value decomposition. The singular values $\sigma_1 \ge \cdots \ge \sigma_p \ge 0$ are uniquely determined by $A$ . The singular vectors are unique up to: 1. sign (or unit-modulus phase) when the corresponding singular value is simple and nonzero; 2. an orthogonal/unitary rotation within each eigenspace when a singular value is repeated.

TheoremRelation to Eigendecomposition

The singular values of $A$ are the nonnegative square roots of the eigenvalues of $A^{*}A$ (equivalently $AA^{*}$ ):

4

\quad A^{*}A = V\,\Sigma^{*}\Sigma\,V^{*}, \qquad AA^{*} = U\,\Sigma\Sigma^{*}\,U^{*}

Derivation hint: substitute $A = U\Sigma V^{*}$ and use $U^{*}U = I$ , $V^{*}V = I$ ; the cross terms collapse leaving diagonal Gram matrices. Thus the right singular vectors $v_i$ are eigenvectors of $A^{*}A$ , the left singular vectors $u_i$ are eigenvectors of $AA^{*}$ , and $\sigma_i^2$ are the shared nonzero eigenvalues.

ProofExistence of the SVD

We construct the decomposition explicitly.

Step 1 — Symmetrize. Form $A^{*}A \in \mathbb{C}^{n\times n}$ . This matrix is Hermitian and positive semidefinite: for any $x$ , $x^{*}(A^{*}A)x = \|Ax\|^2 \ge 0$ .

Step 2 — Apply the spectral theorem. Because $A^{*}A$ is Hermitian, it has an orthonormal eigenbasis $v_1,\dots,v_n$ with real eigenvalues $\lambda_1 \ge \cdots \ge \lambda_n \ge 0$ . Define $\sigma_i = \sqrt{\lambda_i}$ . Let $r$ be the number of strictly positive eigenvalues.

Step 3 — Define left singular vectors. For $i = 1,\dots,r$ set

5

\quad u_i = \frac{1}{\sigma_i}\,A v_i

Derivation hint: this normalizes $Av_i$ ; check $\|u_i\|=1$ using $\|Av_i\|^2 = v_i^{*}A^{*}A v_i = \lambda_i$ .

Step 4 — Verify orthonormality of the $u_i$ . Compute

6

\quad u_i^{*}u_j = \frac{1}{\sigma_i\sigma_j}\,v_i^{*}A^{*}A\,v_j = \frac{\lambda_j}{\sigma_i\sigma_j}\,v_i^{*}v_j = \frac{\lambda_j}{\sigma_i\sigma_j}\,\delta_{ij} = \delta_{ij}

Derivation hint: use $A^{*}A v_j = \lambda_j v_j$ then orthonormality $v_i^{*}v_j = \delta_{ij}$ and $\lambda_i = \sigma_i^2$ . So $\{u_1,\dots,u_r\}$ is orthonormal in $\mathbb{C}^m$ .

Step 5 — Complete the bases. Extend $\{u_i\}_{i\le r}$ to an orthonormal basis $u_1,\dots,u_m$ of $\mathbb{C}^m$ (Gram–Schmidt). Set the remaining $\sigma_i = 0$ . The $v_i$ already form a full orthonormal basis of $\mathbb{C}^n$ .

Step 6 — Assemble. By construction $Av_i = \sigma_i u_i$ for all $i$ (for $i>r$ , $Av_i = 0$ since $\lambda_i = 0$ ). Collecting columns, $AV = U\Sigma$ , hence $A = U\Sigma V^{*}$ since $V$ is unitary. $\blacksquare$

∎

ProofUniqueness of Singular Values

Suppose $A = U\Sigma V^{*}$ . Then $A^{*}A = V\Sigma^2 V^{*}$ , which exhibits $\sigma_i^2$ as the eigenvalues of $A^{*}A$ . Eigenvalues are invariants of a matrix, independent of any factorization. Hence the multiset $\{\sigma_i^2\}$ , and therefore $\{\sigma_i\}$ as ordered nonnegative reals, is uniquely determined by $A$ . $\blacksquare$

∎

mathematician · Eugenio Beltrami | 1835–1900

The Italian mathematician Eugenio Beltrami first derived the singular value decomposition in 1873 for real square matrices, motivated by the study of bilinear forms and their invariants under change of basis. He sought a canonical form for a bilinear form $\sum a_{ij}x_i y_j$ under independent orthogonal substitutions of the $x$ and $y$ variables — exactly the geometry of $U$ and $V$ . Camille Jordan rediscovered it independently in 1874, and the theory was later extended by Sylvester, Autonne (to complex matrices, 1915), and Eckart–Young, who in 1936 proved the celebrated low-rank approximation theorem that made the SVD indispensable to applied mathematics.

🧠 Intuition

Picture the unit sphere in $\mathbb{R}^n$ . A general linear map $A$ deforms it into an ellipsoid in $\mathbb{R}^m$ . The SVD reads off the geometry of that ellipsoid directly:

The right singular vectors $v_i$ are the directions on the input sphere that map onto the ellipsoid's principal axes.
The singular values $\sigma_i$ are the lengths of those semi-axes — how far the sphere stretches in each principal direction.
The left singular vectors $u_i$ are the output directions in which the principal axes point.

The largest singular value $\sigma_1$ is the maximum stretch factor; it equals the operator norm $\|A\|_2 = \max_{\|x\|=1}\|Ax\|$ . The smallest nonzero singular value measures how close $A$ is to being rank-deficient. The ratio $\sigma_1/\sigma_r$ is the condition number, governing how sensitively the output reacts to input perturbations.

Figure

The geometry of SVD: a unit circle (right singular vectors) maps to an ellipse whose semi-axes are the singular values along the left singular vectors.

GR

Geometric reading

Engineers often think of $\Sigma$ as a gain spectrum: feed orthogonal "modes" $v_i$ into the system $A$ and they emerge as orthogonal modes $u_i$ amplified by gains $\sigma_i$ . A signal aligned with $v_1$ comes out strongest; one aligned with $v_r$ comes out weakest. Noise hidden in directions with tiny $\sigma_i$ is what makes inverse problems unstable — which is precisely why regularization throttles small singular values.

ExampleA 2×2 matrix by hand

Given: $A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}$ . Find its singular values.

Step 1 — Form $A^{T}A$ :

7

\quad A^{T}A = \begin{pmatrix} 3 & 4 \\ 0 & 5 \end{pmatrix}\begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix} = \begin{pmatrix} 25 & 20 \\ 20 & 25 \end{pmatrix}

Derivation hint: multiply $A^T$ (rows = columns of $A$ ) by $A$ ; the $(1,1)$ entry is $3^2+4^2=25$ .

Step 2 — Eigenvalues of $A^{T}A$ : Solve $\det(A^TA - \lambda I)=0$ :

8

\quad (25-\lambda)^2 - 400 = 0 \;\Rightarrow\; 25-\lambda = \pm 20 \;\Rightarrow\; \lambda = 45,\; 5

Derivation hint: a matrix $\begin{pmatrix}a&b\\b&a\end{pmatrix}$ has eigenvalues $a\pm b$ .

Step 3 — Singular values: $\sigma_1 = \sqrt{45} = 3\sqrt5 \approx 6.708$ , $\sigma_2 = \sqrt5 \approx 2.236$ .

Check: product $\sigma_1\sigma_2 = \sqrt{45\cdot5} = \sqrt{225} = 15 = |\det A| = |3\cdot5 - 0\cdot4|$ . ✓

\boxed{\sigma_1 = 3\sqrt5 \approx 6.71,\qquad \sigma_2 = \sqrt5 \approx 2.24}

ExampleBest rank-1 approximation

Given: $A = \begin{pmatrix} 2 & 2 \\ -1 & 1 \end{pmatrix}$ . Build its rank-1 SVD approximation.

Step 1 — $A^{T}A$ and eigenvalues:

9

\quad A^{T}A = \begin{pmatrix} 5 & 3 \\ 3 & 5 \end{pmatrix},\qquad \lambda = 8,\;2 \;\Rightarrow\; \sigma_1 = 2\sqrt2,\;\sigma_2 = \sqrt2

Derivation hint: $(5-\lambda)^2 = 9$ gives $\lambda = 5\pm3$ .

Step 2 — Right singular vectors (eigenvectors of $A^TA$ ):

10

\quad v_1 = \tfrac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix},\qquad v_2 = \tfrac{1}{\sqrt2}\begin{pmatrix}1\\-1\end{pmatrix}

Derivation hint: for $\lambda=8$ solve $(A^TA-8I)v=0$ , giving $v_1\propto(1,1)$ .

Step 3 — Left singular vectors via $u_i = Av_i/\sigma_i$ :

11

\quad u_1 = \frac{1}{2\sqrt2}\,A v_1 = \frac{1}{2\sqrt2}\begin{pmatrix} 2\sqrt2 \\ 0 \end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix}

Derivation hint: $Av_1 = \tfrac1{\sqrt2}(4,0)^T = (2\sqrt2,0)^T$ , then divide by $\sigma_1 = 2\sqrt2$ .

Step 4 — Rank-1 approximation $A_1 = \sigma_1 u_1 v_1^{T}$ :

12

\quad A_1 = 2\sqrt2\begin{pmatrix}1\\0\end{pmatrix}\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\end{pmatrix} = \begin{pmatrix} 2 & 2 \\ 0 & 0 \end{pmatrix}

Derivation hint: $2\sqrt2 \cdot \tfrac1{\sqrt2} = 2$ ; the outer product places $2$ in the top row.

Approximation error (Frobenius) $= \sigma_2 = \sqrt2 \approx 1.414$ .

\boxed{A_1 = \begin{pmatrix} 2 & 2 \\ 0 & 0 \end{pmatrix},\quad \|A - A_1\|_F = \sqrt2}

⚠️ SVD is not the eigendecomposition

A frequent error is conflating singular values with eigenvalues. They coincide only when $A$ is symmetric positive semidefinite. In general:

Eigenvalues can be negative or complex; singular values are always real and nonnegative.
Eigenvectors need not be orthogonal; singular vectors always are.
The eigendecomposition $A = X\Lambda X^{-1}$ may not exist (defective matrices); the SVD always exists.

For a symmetric matrix with a negative eigenvalue $\lambda = -3$ , the corresponding singular value is $|{-3}| = 3$ , with a sign absorbed into a singular vector.

CounterexampleA matrix with no real eigenvalues but a clean SVD

The rotation matrix

13

\quad R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}

Derivation hint: $R^TR = I$ , so all singular values equal 1; eigenvalues are $\pm i$ . has complex eigenvalues $\pm i$ and no real eigenvectors — its eigenanalysis over $\mathbb{R}$ is empty. Yet its SVD is trivial: since $R^{T}R = I$ , every singular value equals $1$ , and $R = R \cdot I \cdot I$ is already an SVD. The matrix is a pure rotation: it stretches nothing, only turns the plane. This shows the SVD captures geometry that eigenvalues miss entirely.

⚠️ Singular values are sorted, but vectors are not unique

Repeated singular values produce non-unique singular vectors: any orthonormal rotation within the shared subspace is valid. For the identity matrix $I_2$ , every orthonormal pair $(v_1, v_2)$ works as right singular vectors. Never assume your computed $U$ and $V$ match someone else's down to signs — only the $\sigma_i$ are canonical.

connection

The SVD sits at the crossroads of several fundamental topics:

It generalizes the Spectral Theorem: for symmetric PSD matrices the two decompositions coincide.
It defines the Moore-Penrose Pseudoinverse via $A^{+} = V\Sigma^{+}U^{*}$ , where $\Sigma^{+}$ inverts the nonzero singular values.
It underlies Principal Component Analysis: the principal components are the right singular vectors of the mean-centered data matrix.
It computes all four Fundamental Subspaces at once: columns of $U$ split into range and left null space; columns of $V$ split into row space and null space.
It quantifies stability through the Condition Number $\kappa_2(A) = \sigma_1/\sigma_r$ .
It is the engine of Least Squares solutions when the normal equations are ill-conditioned.

🔬 Where this appears

⏳ History

- 1873 — Beltrami. Derives the SVD for real square matrices from the theory of bilinear forms.

- 1874 — Jordan. Independently obtains the decomposition, also studying canonical forms of bilinear forms.

- 1889 — Sylvester. Reaches the same result for real matrices and introduces the term "canonical multipliers."

- 1902–1915 — Autonne. Extends the SVD to complex and rectangular matrices, connecting it to polar decomposition.

- 1907 — Schmidt. Develops the infinite-dimensional analog for integral operators (the Hilbert–Schmidt theory), giving the optimal low-rank approximation in that setting.

- 1936 — Eckart & Young. Prove that truncating the SVD yields the best low-rank approximation in the Frobenius norm — the theorem that powers data science today.

- 1955 — Mirsky. Generalizes Eckart–Young to all unitarily invariant norms, including the spectral norm.

- 1965 — Golub & Kahan. Publish the first stable numerical algorithm (Golub–Kahan bidiagonalization), making SVD practical on computers.

- 1970 — Golub & Reinsch. Refine the algorithm into the standard routine still used in LAPACK and NumPy today.

open-problem

Several practical and theoretical frontiers remain active:

Large-scale and streaming SVD. Computing even a truncated SVD of a billion-row matrix is costly; randomized SVD algorithms (Halko–Martinsson–Tropp, 2011) approximate the top components quickly, but optimal bounds for adversarial or streaming data are still studied.
Tensor generalizations. There is no single canonical SVD for tensors of order $\ge 3$ ; competing notions (CP decomposition, Tucker/HOSVD) trade off uniqueness, computability, and best-approximation guarantees, and finding best low-rank tensor approximations can be NP-hard and even ill-posed.
Perturbation theory. While singular values are stable (Weyl's inequality bounds their shift by $\|E\|_2$ ), singular vectors tied to closely-spaced singular values can swing wildly under perturbation — quantified by the gap-dependent Davis–Kahan and Wedin theorems.
Sparse and structured SVD. Enforcing sparsity or nonnegativity (NMF) destroys orthogonality and the clean optimization landscape, leaving heuristic algorithms without global guarantees.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also