The Singular Value Decomposition

The spectral theorem diagonalizes symmetric matrices with orthonormal eigenvectors. The singular value decomposition does something like it for every matrix, square or not: it finds orthonormal input directions that $A$ sends to orthogonal output directions.

Key idea

Every $m \times n$ matrix factors as $A = U\Sigma V^{T}$, with $U$ ($m \times m$) and $V$ ($n \times n$) orthogonal and $\Sigma$ ($m \times n$) zero except for $\sigma_1 \geq \sigma_2 \geq \cdots \geq 0$ on its diagonal. The singular values $\sigma_i$ are the square roots of the eigenvalues of $A^{T}A$; the columns $\mathbf{v}_i$ of $V$ are orthonormal eigenvectors of $A^{T}A$, and $\mathbf{u}_i = A\mathbf{v}_i/\sigma_i$ for each $\sigma_i > 0$.

Why it works

$A^{T}A$ is symmetric, so it has orthonormal eigenvectors $\mathbf{v}_1, \dots, \mathbf{v}_n$ with eigenvalues $\lambda_i$. They are never negative: $\lambda_i$ $= \mathbf{v}_i^{T}A^{T}A\mathbf{v}_i$ $= \lVert A\mathbf{v}_i\rVert^{2} \geq 0$. So $\lVert A\mathbf{v}_i\rVert = \sqrt{\lambda_i} = \sigma_i$. And the images are orthogonal: $(A\mathbf{v}_i)\cdot(A\mathbf{v}_j)$ $= \mathbf{v}_i^{T}A^{T}A\mathbf{v}_j$ $= \lambda_j\,\mathbf{v}_i\cdot\mathbf{v}_j$ $= 0$ for $i \neq j$. Dividing by their lengths gives orthonormal $\mathbf{u}_i$ with $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$; in matrix form $AV = U\Sigma$, so $A = U\Sigma V^{T}$ (extend the $\mathbf{u}$'s to a full orthonormal basis if needed).

Any $2 \times 2$ matrix sends the unit circle to an ellipse. $V^{T}$ turns, $\Sigma$ stretches the axes by $\sigma_1$ and $\sigma_2$, and $U$ turns again. The right singular vectors $\mathbf{v}_1, \mathbf{v}_2$ land on the ellipse's axes.

Worked example: An SVD by hand

Find the SVD of $A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}$.

$A^{T}A = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}$: trace $50$, determinant $625 - 400 = 225$, so $\lambda^{2} - 50\lambda + 225 = (\lambda - 45)(\lambda - 5)$.
$\sigma_1 = \sqrt{45} = 3\sqrt{5}$ and $\sigma_2 = \sqrt{5}$. Check: $\sigma_1\sigma_2 = 15 = |\det A|$.
Eigenvectors of $A^{T}A$: $\mathbf{v}_1 = \frac{1}{\sqrt{2}}(1, 1)$ for $45$ and $\mathbf{v}_2 = \frac{1}{\sqrt{2}}(-1, 1)$ for $5$.
$A\mathbf{v}_1 = \frac{1}{\sqrt{2}}(3, 9)$, so $\mathbf{u}_1$ $= \dfrac{A\mathbf{v}_1}{3\sqrt{5}}$ $= \frac{1}{\sqrt{10}}(1, 3)$. $A\mathbf{v}_2 = \frac{1}{\sqrt{2}}(-3, 1)$, so $\mathbf{u}_2 = \frac{1}{\sqrt{10}}(-3, 1)$.
$U = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 & -3 \\ 3 & 1 \end{bmatrix}$, $\Sigma = \begin{bmatrix} 3\sqrt{5} & 0 \\ 0 & \sqrt{5} \end{bmatrix}$, $V = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}$.

Answer: $\sigma_1 = 3\sqrt{5}$, $\sigma_2 = \sqrt{5}$

What the SVD tells you at a glance: $\operatorname{rank} A$ is the number of nonzero singular values; $\mathbf{u}_1, \dots, \mathbf{u}_r$ are an orthonormal basis of $\operatorname{Col} A$ and $\mathbf{v}_{r+1}, \dots, \mathbf{v}_n$ of $\operatorname{Nul} A$; and $\sigma_1$ is the largest stretch, $\max \lVert A\mathbf{x}\rVert$ over unit vectors $\mathbf{x}$.

Worked example: Eigenvalues are not singular values

$A = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}$ has eigenvalues $1, 1$. Find its singular values.

$A^{T}A = \begin{bmatrix} 1 & 2 \\ 2 & 5 \end{bmatrix}$, with $\lambda^{2} - 6\lambda + 1 = 0$, so $\lambda = 3 \pm 2\sqrt{2}$.
$3 + 2\sqrt{2} = (1 + \sqrt{2})^{2}$, so $\sigma_1 = 1 + \sqrt{2} \approx 2.414$ and $\sigma_2 = \sqrt{2} - 1 \approx 0.414$.
This shear stretches some vectors by $2.4$ and shrinks others to $0.4$ of their length, even though both eigenvalues are $1$.

Answer: $1 + \sqrt{2}$ and $\sqrt{2} - 1$

Common mistake

Taking the singular values to be the eigenvalues of $A$. They agree only for special matrices (symmetric with nonnegative eigenvalues). In general use the square roots of the eigenvalues of $A^{T}A$. Checks: singular values are never negative, and for a square matrix their product is $|\det A|$.

For a wide matrix ($m < n$) it is quicker to find the eigenvalues of the smaller matrix $AA^{T}$: its nonzero eigenvalues are the same as those of $A^{T}A$.

The Singular Value Decomposition

Practice

Builds on

Leads to

Sources and further reading