Singular Value Decomposition

A square matrix with $n$ linearly independent eigenvectors factors into a product that separates directions from scalings. That factorization requires the matrix to be square and to have a full set of eigenvectors. For a rectangular matrix, eigenvalues are not defined, because the input space and the output space have different dimensions. Singular value decomposition provides a factorization of any matrix, square or rectangular, with no condition on eigenvectors or invertibility.

Let $A$ be an $m \times n$ real matrix of rank $r$. The singular value decomposition of $A$ is

\[A = U \Sigma V^\top\]

where $U$ is an $m \times m$ orthogonal matrix, $V$ is an $n \times n$ orthogonal matrix, and $\Sigma$ is an $m \times n$ matrix whose only nonzero entries lie on the main diagonal. Those diagonal entries $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$ are the singular values of $A$. The columns of $U$ are the left singular vectors. The columns of $V$ are the right singular vectors. Every real matrix has such a decomposition.

The factorization follows from the eigendecomposition of $A^\top A$. This matrix is $n \times n$, symmetric, and positive semidefinite, so all its eigenvalues are nonnegative. The singular values of $A$ are the positive square roots of the nonzero eigenvalues of $A^\top A$. The corresponding eigenvectors, after normalization, form the columns of $V$. Each left singular vector is given by $\mathbf{u}_i = A\mathbf{v}_i / \sigma_i$ for $i = 1, \ldots, r$. When $m > r$, the remaining columns of $U$ are any orthonormal vectors that complete a basis for $\mathbb{R}^m$.

Take a concrete case. Let

\[A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix}.\]

Then \(A^\top A = \bigl[\begin{smallmatrix} 2 & 1 \\ 1 & 2 \end{smallmatrix}\bigr]\). The characteristic equation is $(2 - \lambda)^2 - 1 = 0$, giving eigenvalues 3 and 1. The singular values are $\sigma_1 = \sqrt{3}$ and $\sigma_2 = 1$. For the eigenvalue 3, the normalized eigenvector is $\mathbf{v}_1 = (1,\, 1)^\top / \sqrt{2}$. For the eigenvalue 1, it is $\mathbf{v}_2 = (1,\, -1)^\top / \sqrt{2}$. These form the columns of $V$. The left singular vectors are $\mathbf{u}_1 = A\mathbf{v}_1 / \sqrt{3} = (2,\, 1,\, 1)^\top / \sqrt{6}$ and $\mathbf{u}_2 = A\mathbf{v}_2 = (0,\, -1,\, 1)^\top / \sqrt{2}$. A third column $\mathbf{u}_3 = (1,\, -1,\, -1)^\top / \sqrt{3}$, orthogonal to both, completes $U$. The matrix $\Sigma$ is $3 \times 2$ with $\sqrt{3}$ and $1$ on the diagonal and zeros elsewhere.

The singular values determine how much the matrix stretches unit vectors along the principal directions defined by $V$. The largest singular value $\sigma_1$ equals the maximum of $\lVert A\mathbf{x} \rVert$ over all unit vectors $\mathbf{x}$. The number of nonzero singular values equals the rank. Setting the smallest singular values to zero and keeping only the largest $k$ gives the rank-$k$ matrix closest to $A$ in the Frobenius norm. The Frobenius norm of a matrix is the square root of the sum of all its squared entries. This fact, the Eckart-Young theorem, is the theoretical basis of low-rank approximation in data compression and dimensionality reduction. When $A$ is square and invertible, the ratio $\sigma_1 / \sigma_r$ is the condition number, which quantifies how sensitive the solution of $A\mathbf{x} = \mathbf{b}$ is to perturbations in $\mathbf{b}$.