The singular value decomposition
Every matrix, square or not, can be factored into rotations and stretches. The singular value decomposition is perhaps the most useful factorisation in applied mathematics.
The decomposition
Every m x n matrix A can be written \(A = U\Sigma V^T\), where U (m x m) and V (n x n) are orthogonal and \(\Sigma\) is m x n with non-negative singular values \(\sigma_1 \ge \sigma_2 \ge \dots \ge 0\) on its diagonal. Geometrically, A rotates (by \(V^T\)), stretches along axes (by \(\Sigma\)), and rotates again (by U). Unlike eigendecomposition, it exists for every matrix.
Computing singular values
The singular values are the square roots of the eigenvalues of the symmetric matrix \(A^TA\). The columns of V are orthonormal eigenvectors of \(A^TA\) (right singular vectors), and the columns of U are \(\mathbf{u}_i = \frac{A\mathbf{v}_i}{\sigma_i}\) for non-zero \(\sigma_i\) (left singular vectors), extended to an orthonormal basis if needed. In practice, stable algorithms such as Golub-Kahan bidiagonalisation (1965) compute the SVD directly.
What the SVD reveals
The number of non-zero singular values is the rank. The first r columns of U form an orthonormal basis of Col A, and the first r columns of V of Row A; the remaining columns give bases of the null spaces. The largest singular value is the maximum stretching factor, the operator 2-norm, and the ratio of largest to smallest gives the condition number.
Low-rank approximation
Writing \(A = \sigma_1\mathbf{u}_1\mathbf{v}_1^T + \dots + \sigma_r\mathbf{u}_r\mathbf{v}_r^T\) and keeping only the first k terms gives \(A_k\), the best rank-k approximation of A, by the Eckart-Young theorem (1936). Because singular values often decay quickly, a few terms capture most of a matrix's structure, enabling compression and noise reduction.
Principal component analysis
In principal component analysis (PCA), developed by Karl Pearson in 1901 and Harold Hotelling in 1933, data are centred and the SVD of the data matrix is computed. The right singular vectors give principal directions of greatest variance, and squared singular values measure variance along them. Projecting onto the first few components reduces dimension while keeping most of the information.
The pseudoinverse
The Moore-Penrose pseudoinverse is \(A^+ = V\Sigma^+U^T\), where \(\Sigma^+\) inverts the non-zero singular values. For any system, \(\hat{\mathbf{x}} = A^+\mathbf{b}\) is the least-squares solution of smallest length, even when A is rank-deficient. Numerical software computes rank and pseudoinverses from the SVD, treating singular values below a tolerance as zero.
Applications
The SVD compresses images by keeping leading singular components, powers recommendation systems (the Netflix Prize of 2006 to 2009 popularised matrix factorisation methods), underlies latent semantic analysis of text, denoises signals, solves ill-conditioned least-squares problems, and is used in control, robotics, and quantum information. It has been called the Swiss Army knife of numerical linear algebra.
Worked example
For \(A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}\), \(A^TA = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}\), with eigenvalues 45 and 5. So the singular values are \(\sigma_1 = \sqrt{45} = 3\sqrt{5} \approx 6.71\) and \(\sigma_2 = \sqrt{5} \approx 2.24\). Their product is 15, equal to \(|\det A| = 15\), and A stretches some direction by about 6.71 and the perpendicular one by about 2.24; its condition number is 3.
Key takeaways
Every matrix has an SVD, A = U Sigma V^T, with orthogonal U and V and non-negative singular values in decreasing order: rotate, stretch, rotate. Singular values are square roots of eigenvalues of A^T A; V holds right singular vectors and U = A v_i / sigma_i the left ones; Golub-Kahan (1965) computes them stably. The SVD gives rank, bases of the four fundamental subspaces, the 2-norm, and the condition number. Truncating gives the best rank-k approximation (Eckart-Young, 1936). PCA (Pearson 1901, Hotelling 1933) uses the SVD of centred data. The pseudoinverse V Sigma^+ U^T gives minimum-length least-squares solutions. Applications include compression, recommendations, text analysis, and denoising.
Flashcard
A = U Sigma V^T
Check your understanding
Why can an image be compressed well by keeping only the first few terms of its SVD?