7.4 The singular value decomposition

Big idea

Diagonalization needs a square matrix, and even then it can fail. Most matrices in practice are rectangular: rows are measurements, columns are variables, and there are more of one than the other. Such a matrix has no eigenvalues at all, since $A\mathbf{x} = \lambda\mathbf{x}$ does not even typecheck when $A$ is not square.

The repair is to stop asking for one basis and ask for two. Look for orthonormal vectors $\mathbf{v}_1, \dots, \mathbf{v}_n$ in the input space and orthonormal vectors $\mathbf{u}_1, \dots, \mathbf{u}_m$ in the output space such that $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$. Each input direction goes to an output direction, stretched by a number. That is the same “scale along special directions” story as before, with the input and output directions allowed to differ.

Those directions are not hard to find, because $A^{T}A$ is symmetric and the previous sections already solved symmetric matrices. Its orthonormal eigenvectors are the $\mathbf{v}_i$, the square roots of its eigenvalues are the stretch factors, and the $\mathbf{u}_i$ follow by applying $A$. Every matrix, of every shape, factors this way. No exceptions and no conditions.

Decoder

The singular values of $A$ are the square roots of the eigenvalues of $A^{T}A$, arranged in decreasing order, and they are the lengths of the vectors $A\mathbf{v}_i$.

Two claims in one sentence. The first is a recipe: build $A^{T}A$, which is square and symmetric no matter what shape $A$ had, find its eigenvalues, take square roots. That is legal because those eigenvalues are never negative. The second claim says what the numbers mean: $\sigma_i$ is how far the unit vector $\mathbf{v}_i$ travels under $A$. Largest singular value first is a convention, but everything downstream assumes it.

Definitions and results

Why $A^{T}A$ is the right object. For any $m \times n$ matrix $A$, the product $A^{T}A$ is $n \times n$ and symmetric, since $(A^{T}A)^{T} = A^{T}A$. It is also positive semidefinite: for any $\mathbf{x}$,

$$ \mathbf{x}^{T}(A^{T}A)\mathbf{x} = (A\mathbf{x})^{T}(A\mathbf{x}) = \|A\mathbf{x}\|^2 \geq 0 $$

so no eigenvalue is negative, and square roots are available.

Singular values. With the eigenvalues of $A^{T}A$ ordered as $\lambda_1 \geq \cdots \geq \lambda_n \geq 0$ and unit eigenvectors $\mathbf{v}_1, \dots, \mathbf{v}_n$, the singular values are $\sigma_i = \sqrt{\lambda_i}$. Taking $\mathbf{x} = \mathbf{v}_i$ in the identity above gives $|A\mathbf{v}_i|^2 = \lambda_i$, so $\sigma_i = \|A\mathbf{v}_i\|$.

Singular values are not eigenvalues. Even for a square matrix the two lists usually differ. They agree when $A$ is symmetric and positive semidefinite, and in general the product of all singular values of a square $A$ equals $|\det A|$.

Rank. If $A$ has exactly $r$ nonzero singular values, then the vectors $A\mathbf{v}_1, \dots, A\mathbf{v}_r$ form an orthogonal basis for the column space of $A$, so the rank of $A$ is $r$. The orthogonality is a one-line computation: for $i \neq j$, $(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$. A zero singular value means $A\mathbf{v}_i = \mathbf{0}$, so those $\mathbf{v}_i$ span the null space.

Singular value decomposition. Every $m \times n$ matrix $A$ factors as

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

where $U$ is $m \times m$ orthogonal, $V$ is $n \times n$ orthogonal, and $\Sigma$ is $m \times n$ with $\sigma_1, \dots, \sigma_r$ down the start of its main diagonal and zeros everywhere else. The columns of $V$ are the right singular vectors, the columns of $U$ are the left singular vectors.

The construction. Diagonalize $A^{T}A$ orthogonally to get $\mathbf{v}_1, \dots, \mathbf{v}_n$ ordered by decreasing eigenvalue. For each $i \leq r$ set $\mathbf{u}_i = A\mathbf{v}_i / \sigma_i$; these are orthonormal by the computation above. If $r < m$, extend them to an orthonormal basis of $\mathbb{R}^m$, for instance by Gram-Schmidt on any spanning set. Fill $\Sigma$ with the singular values. The factorization then holds column by column, since $AV = U\Sigma$ says exactly $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$, and multiplying on the right by $V^{T} = V^{-1}$ finishes it.

Four subspaces at once. With $r$ nonzero singular values: $\mathbf{u}_1, \dots, \mathbf{u}r$ is an orthonormal basis for the column space of $A$; $\mathbf{u}_{r+1}, \dots, \mathbf{u}_m$ for the null space of $A^{T}$; $\mathbf{v}_1, \dots, \mathbf{v}_r$ for the row space; and $\mathbf{v}{r+1}, \dots, \mathbf{v}_n$ for the null space of $A$. One factorization answers every subspace question about $A$.

Reduced form and rank-one pieces. Dropping the columns of $U$ and $V$ that meet only zeros gives $A = U_r D V_r^{T}$ with $D$ the $r \times r$ diagonal of nonzero singular values. Expanding that product gives

$$ A = \sigma_1\mathbf{u}_1\mathbf{v}_1^{T} + \cdots + \sigma_r\mathbf{u}_r\mathbf{v}_r^{T} $$

a sum of rank-one matrices in decreasing order of importance. The next section uses that ordering.

Worked examples

A two by two, start to finish

Take

$$ A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} $$

Step one, build $A^{T}A$. The columns of $A$ are $(3,4)$ and $(0,5)$, so the entries are their dot products:

$$ A^{T}A = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix} $$

Step two, its eigenvalues: $(25 - \lambda)^2 - 400 = 0$ gives $\lambda = 45$ and $\lambda = 5$. So $\sigma_1 = \sqrt{45} = 3\sqrt{5}$ and $\sigma_2 = \sqrt{5}$. Check against the determinant: $\sigma_1\sigma_2 = 3 \cdot 5 = 15$, and $\det A = 15 - 0 = 15$.

Step three, the right singular vectors. For $\lambda = 45$ the system $(A^{T}A - 45I)\mathbf{x} = \mathbf{0}$ has coefficient matrix $\begin{bmatrix} -20 & 20 \\ 20 & -20 \end{bmatrix}$, so $\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1,1)$. For $\lambda = 5$ the same computation gives $\mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(1,-1)$.

Step four, the left singular vectors. Apply $A$ and divide by the singular value:

$$ A\mathbf{v}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 3 \\ 9 \end{bmatrix}, \qquad \mathbf{u}_1 = \frac{1}{3\sqrt{5}} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 3 \\ 9 \end{bmatrix} = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 \\ 3 \end{bmatrix} $$

$$ A\mathbf{v}_2 = \frac{1}{\sqrt{2}}\begin{bmatrix} 3 \\ -1 \end{bmatrix}, \qquad \mathbf{u}_2 = \frac{1}{\sqrt{5}} \cdot \frac{1}{\sqrt{2}}\begin{bmatrix} 3 \\ -1 \end{bmatrix} = \frac{1}{\sqrt{10}}\begin{bmatrix} 3 \\ -1 \end{bmatrix} $$

Both have length one, since $1 + 9 = 10$ and $9 + 1 = 10$, and they are perpendicular: $1(3) + 3(-1) = 0$. So

$$ U = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 & 3 \\ 3 & -1 \end{bmatrix}, \qquad \Sigma = \begin{bmatrix} 3\sqrt{5} & 0 \\ 0 & \sqrt{5} \end{bmatrix}, \qquad V = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} $$

Multiply back to check. First

$$ U\Sigma = \frac{1}{\sqrt{10}}\begin{bmatrix} 3\sqrt{5} & 3\sqrt{5} \\ 9\sqrt{5} & -\sqrt{5} \end{bmatrix} $$

then multiply by $V^{T}$, which is $V$ itself here:

$$ U\Sigma V^{T} = \frac{1}{\sqrt{20}}\begin{bmatrix} 6\sqrt{5} & 0 \\ 8\sqrt{5} & 10\sqrt{5} \end{bmatrix} = \frac{1}{2\sqrt{5}}\begin{bmatrix} 6\sqrt{5} & 0 \\ 8\sqrt{5} & 10\sqrt{5} \end{bmatrix} = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} $$

The original matrix, so the decomposition is right. Note what the eigenvalues of $A$ itself are: $3$ and $5$, since $A$ is triangular. Neither equals a singular value, though the products match at $15$.

A wide matrix, with the null space read off

Take

$$ C = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} $$

Then

$$ C^{T}C = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{bmatrix} $$

Guess and verify rather than expanding a cubic. Applying $C^{T}C$ to $(1,1,2)$ gives $(3,3,6)$, so $\lambda = 3$. Applying it to $(1,-1,0)$ gives $(1,-1,0)$, so $\lambda = 1$. Applying it to $(1,1,-1)$ gives $(0,0,0)$, so $\lambda = 0$. The three vectors are mutually perpendicular and the trace check holds: $3 + 1 + 0 = 4 = 1 + 1 + 2$.

So the singular values are $\sigma_1 = \sqrt{3}$ and $\sigma_2 = 1$, the rank is $2$, and the normalized right singular vectors are

$$ \mathbf{v}_1 = \frac{1}{\sqrt{6}}(1,1,2), \qquad \mathbf{v}_2 = \frac{1}{\sqrt{2}}(1,-1,0), \qquad \mathbf{v}_3 = \frac{1}{\sqrt{3}}(1,1,-1) $$

The last one spans the null space of $C$, which you can confirm without any of this machinery: $C(1,1,-1) = (1 + 0 - 1, \; 0 + 1 - 1) = (0,0)$.

For the left singular vectors, $C(1,1,2) = (3,3)$, so

$$ \mathbf{u}_1 = \frac{1}{\sqrt{3}} \cdot \frac{1}{\sqrt{6}}\begin{bmatrix} 3 \\ 3 \end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix} $$

and $C(1,-1,0) = (1,-1)$, so $\mathbf{u}_2 = \tfrac{1}{\sqrt{2}}(1,-1)$. Two orthonormal vectors in $\mathbb{R}^2$, so $U$ is complete with no extension needed, and $\Sigma$ is the $2 \times 3$ matrix with $\sqrt{3}$ and $1$ on the diagonal and a zero column at the end.

Check the first row of the product. The first row of $U\Sigma$ is $(\sqrt{3}/\sqrt{2}, \; 1/\sqrt{2}, \; 0)$, and multiplying by $V^{T}$ combines the rows of $V^{T}$ with those weights:

$$ \frac{\sqrt{3}}{\sqrt{2}} \cdot \frac{(1,1,2)}{\sqrt{6}} + \frac{1}{\sqrt{2}} \cdot \frac{(1,-1,0)}{\sqrt{2}} = \frac{(1,1,2)}{2} + \frac{(1,-1,0)}{2} = (1, 0, 1) $$

which is the first row of $C$. The second row works the same way with the sign of the second term flipped, giving $(0,1,1)$.

Practice

The first step of every decomposition is an eigenvalue computation on $A^{T}A$, so drill that.

$U$ and $V$ are orthogonal matrices, and the check $U^{T}U = I$ is what tells you the singular vectors were normalized correctly.

Building $A^{T}A$ and multiplying $U\Sigma V^{T}$ back together are both plain matrix products, and that is where most arithmetic errors happen.

Videos

The first video builds the factorization from the two-basis idea and is worth the full hour. The second is a short overview that fixes the shapes of $U$, $\Sigma$, and $V$ in your head before you compute one by hand; watch for how the tall and wide cases differ.

Quiz

Six items on singular values from $A^{T}A$, the shapes and properties of the three factors, and the matrix products involved.