svd

Singular Value Decomposition (SVD)

Definition

Every real matrix $A\in {\mathbb{R}}^{m\times n}$ can be factorised as

$$A=U\Sigma V^{\top }$$

where $U\in {\mathbb{R}}^{m\times m}$ and $V\in {\mathbb{R}}^{n\times n}$ are orthogonal matrices and $\Sigma \in {\mathbb{R}}^{m\times n}$ is a diagonal matrix with non-negative entries ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$ (the singular values), $r=\text{rank}(A)$.

Intuition

Every linear map decomposes into three geometric steps: (1) rotate/reflect input space ($V^{\top }$), (2) scale along each axis ($\Sigma$), and (3) rotate/reflect output space ($U$). The singular values ${\sigma }_i$ measure how strongly the map stretches in each direction — the first is the largest and captures the most “action”.

This is the most general matrix factorisation: it always exists, requires no special structure (unlike eigendecomposition), and applies to rectangular matrices.

Formal Description

Thin (economy) SVD: keep only the $r$ non-zero singular values:

$$A=U_r{\Sigma }_r{V}_r^{\top }{U}_r\in {\mathbb{R}}^{m\times r},{\Sigma }_r\in {\mathbb{R}}^{r\times r},V_r\in {\mathbb{R}}^{n\times r}$$

Relationship to eigendecomposition:

$$A^{\top }A=V{\Sigma }^{\top }\Sigma V^{\top }(\text{eigendecomp of }{A}^{\top }A)$$ $$A{A}^{\top }=U\Sigma {\Sigma }^{\top }{U}^{\top }(\text{eigendecomp of }A{A}^{\top })$$

The singular values are ${\sigma }_i=\sqrt{{\lambda }_i(A^{\top }A)}$; the columns of $V$ are eigenvectors of $A^{\top }A$ (right singular vectors); columns of $U$ are eigenvectors of $A{A}^{\top }$ (left singular vectors).

Rank-$k$ approximation (Eckart-Young theorem):

$$A_k=U_k{\Sigma }_k{V}_k^{\top }=\sum _{i=1}^k{\sigma }_i{u}_i{v}_i^{\top }$$

minimises $\Vert A-B{\Vert }_F$ (Frobenius) and $\Vert A-B{\Vert }_2$ (spectral) over all rank-$k$ matrices $B$. The approximation error is $\Vert A-A_k{\Vert }_F^2={\sum }_{i=k+1}^r{\sigma }_i^2$.

Moore-Penrose pseudoinverse:

$$A^{+}=V{\Sigma }^{+}{U}^{\top }$$

where ${\Sigma }^{+}$ replaces each non-zero ${\sigma }_i$ by $1/{\sigma }_i$. Gives the minimum-norm least-squares solution to $A\mathbf{x}=\mathbf{b}$: $\hat{\mathbf{x}}=A^{+}\mathbf{b}$.

Condition number:

$$\kappa (A)=\frac{{\sigma }_{\max }}{{\sigma }_{\min }}$$

A large condition number indicates a near-singular (ill-conditioned) matrix; small perturbations in $\mathbf{b}$ can cause large changes in $\hat{\mathbf{x}}$.

Numerical computation: the Golub-Reinsch algorithm computes SVD in $O(\min (m,n)\cdot mn)$ time via bidiagonalization followed by QR iteration.

Applications

Application	How SVD is used
PCA	Principal components = right singular vectors of centred data matrix $X$; ${\sigma }_i^2/(n-1)$ = variance explained
Low-rank approximation	Compress images, text co-occurrence matrices, recommendation systems
Pseudoinverse / least squares	Solve overdetermined or rank-deficient systems $A\mathbf{x}\approx \mathbf{b}$
Latent Semantic Analysis (LSA)	Compress term-document matrix to $k$ latent semantic dimensions
Noise reduction	Truncate small singular values to remove noise
Numerical linear algebra	Matrix condition estimation, regularization

Trade-offs

• Full SVD costs $O(m^{2}n)$ for $m\ge n$; use randomized SVD (e.g., sklearn.utils.extmath.randomized_svd) for large matrices when only the top-$k$ factors are needed.
• Numerically more stable than eigendecomposition of $A^{\top }A$ (squaring the condition number).
• Rank-$k$ truncation is the globally optimal low-rank approximation — no other rank-$k$ factorisation is better in Frobenius or spectral norm.

Links

• Eigenvalues and Eigenvectors — singular values are eigenvalues of $A^{\top }A$
• Matrix Diagonalization — SVD generalises eigendecomposition to rectangular matrices
• Orthogonal Projections — columns of $U_k$, $V_k$ are orthonormal bases for column/row spaces
• PCA and Unsupervised Learning