Textbook of AI

Also known as: SVD

The singular value decomposition (SVD) factorises any matrix $A \in \mathbb{R}^{m \times n}$ as

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

where $U \in \mathbb{R}^{m \times m}$ is orthogonal ($U^\top U = I$), $V \in \mathbb{R}^{n \times n}$ is orthogonal, and $\Sigma \in \mathbb{R}^{m \times n}$ is diagonal with non-negative entries $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{\min(m,n)} \geq 0$ called the singular values. The columns of $U$ and $V$ are the left and right singular vectors.

The SVD generalises eigendecomposition to non-square matrices and reveals the matrix's geometry: $A$ acts on a unit sphere in $\mathbb{R}^n$ by sending it to an ellipsoid in $\mathbb{R}^m$ with semi-axes given by the singular values along directions $u_i$.

Rank of $A$ equals the number of non-zero singular values. Frobenius norm $\|A\|_F = \sqrt{\sum \sigma_i^2}$. Spectral norm $\|A\|_2 = \sigma_1$. Condition number $\sigma_1 / \sigma_r$ where $r$ is the rank.

Low-rank approximation: the best rank-$k$ approximation to $A$ in Frobenius or spectral norm (the Eckart–Young theorem) is $A_k = U_k \Sigma_k V_k^\top$, the first $k$ singular components. This underlies: Principal component analysis (PCA), SVD of centred data is PCA; Latent semantic indexing, SVD of term-document matrix gives topic structure; Image compression, SVD of image matrix retains visual quality at low rank; Recommender systems, matrix factorisation of user-item ratings (Netflix Prize era); LoRA, fine-tuning by adding a learnable low-rank update $\Delta W = BA$ where $B, A$ are small rank-$r$ matrices.

Numerical computation is by iterative methods (LAPACK's gesdd, randomised SVD for large matrices, Lanczos algorithm for streaming or sparse cases). The randomised SVD (Halko, Martinsson and Tropp, 2011) has been particularly influential in large-scale machine learning.