Singular Value Decomposition

The Singular Value Decomposition expresses an arbitrary $m\times n$ matrix $A$ as a product $A=U\Sigma V^{\ast }$, where the columns of $U$ and $V$ form orthonormal bases of the output and input spaces, and $\Sigma$ holds the singular values — nonnegative real numbers measuring how much $A$ stretches space along principal directions. Unlike eigendecomposition, the SVD exists for every matrix, including rectangular and singular ones, making it the most universal matrix factorization. It matters because it simultaneously reveals rank, null space, range, conditioning, and the optimal low-rank approximation of a matrix. A surprising fact: truncating the SVD after the $k$ largest singular values gives the provably best rank-$k$ approximation in both the spectral and Frobenius norms — a single decomposition solves an entire family of optimization problems.

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^{\ast }$), 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.

Formal Statement

Singular 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

where:

• $U\in {\mathbb{C}}^{m\times m}$ is unitary ($U^{\ast }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^{\ast }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^{\ast }$ denotes the conjugate transpose of $V$ (just the transpose $V^T$ in the real case).

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

Reduced (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:

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.

Existence 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.

Relation to Eigendecomposition

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

Thus the right singular vectors $v_i$ are eigenvectors of $A^{\ast }A$, the left singular vectors $u_i$ are eigenvectors of $A{A}^{\ast }$, and ${\sigma }_i^2$ are the shared nonzero eigenvalues.

Why It Holds / Derivation

Existence of the SVD

We construct the decomposition explicitly.

So $\{u_1,\dots ,u_r\}$ is orthonormal in ${\mathbb{C}}^m$.

Uniqueness of Singular Values

Suppose $A=U\Sigma V^{\ast }$. Then $A^{\ast }A=V{\Sigma }^2{V}^{\ast }$, which exhibits ${\sigma }_i^2$ as the eigenvalues of $A^{\ast }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$. $■$

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.

Building 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 $\Vert A{\Vert }_2={\max }_{\Vert x\Vert =1}\Vert Ax\Vert$. 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.

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.

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.

Worked Examples

A 2×2 matrix by hand

Best rank-1 approximation

Common Misconceptions

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.

A matrix with no real eigenvalues but a clean SVD

The rotation matrix

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.

Connections

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}^{\ast }$, 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.

Real-World Applications

1. Image compression (PCA / Eckart–Young). A grayscale image is a matrix; keeping the top $k$ singular triplets reproduces the image with a fraction of the data. A $512\times 512$ image kept at rank 50 needs roughly $50\cdot (512+512+1)\approx 51,000$ numbers instead of $262,144$.

1. Latent Semantic Analysis (information retrieval). A term–document matrix is truncated via SVD to expose latent topics, letting search engines match "car" to documents about "automobiles."

1. Recommender systems (Netflix Prize). Low-rank SVD-style factorizations of the sparse user–item rating matrix predict unseen ratings; the winning approaches were built on matrix factorization.

1. Principal Component Analysis. Genomics, finance, and face recognition ("eigenfaces") reduce high-dimensional data to its dominant singular directions.

1. Total Least Squares & line/plane fitting. When both coordinates carry error, the best-fit subspace is spanned by the top right singular vectors of the centered data.

1. Numerical rank and noise filtering. Engineers determine the effective rank of a measured matrix by thresholding small singular values — distinguishing signal from noise in control systems and radar.

1. Solving ill-posed inverse problems. Tikhonov regularization and truncated SVD damp the contributions of tiny ${\sigma }_i$, stabilizing deconvolution in tomography and seismology.

Historical Development

• 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.

Subtleties & Limits

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 $\Vert E{\Vert }_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.

See Also