Math Core

Diagonalization only works for some square matrices, and orthogonal diagonalization only for symmetric ones. The singular value decomposition (SVD) works for every matrix, of any shape. It says that any linear map, viewed in the right orthonormal bases for its input and output spaces, simply stretches along perpendicular directions. The SVD powers image compression, principal component analysis, recommendation systems, and the numerical computation of rank.

Singular values

Let $A$ be an $m \times n$ matrix. The matrix $A^TA$ is $n \times n$ and symmetric, so it has an orthonormal eigenbasis $\mathbf{v}_1, \ldots, \mathbf{v}_n$ with real eigenvalues $\lambda_1, \ldots, \lambda_n$ . These eigenvalues are never negative, because for a unit eigenvector $\mathbf{v}_i$ ,

\|A\mathbf{v}_i\|^2 = (A\mathbf{v}_i)^T(A\mathbf{v}_i) = \mathbf{v}_i^T(A^TA\mathbf{v}_i) = \lambda_i\mathbf{v}_i^T\mathbf{v}_i = \lambda_i.

Definition

Singular values

The singular values of $A$ are the square roots of the eigenvalues of $A^TA$ , listed in decreasing order:

\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0, \qquad \sigma_i = \sqrt{\lambda_i}.

By the computation above, $\sigma_i = \|A\mathbf{v}_i\|$ : the singular value is the length of $A$ applied to the unit eigenvector $\mathbf{v}_i$ .

Two more facts follow quickly. First, for $i \ne j$ , $(A\mathbf{v}_i) \cdot (A\mathbf{v}_j) = \mathbf{v}_i^TA^TA\mathbf{v}_j = \lambda_j(\mathbf{v}_i \cdot \mathbf{v}_j) = 0$ , so the vectors $A\mathbf{v}_1, \ldots, A\mathbf{v}_n$ are orthogonal. Second, the nonzero ones among them form a basis for $\operatorname{Col}A$ , so

\operatorname{rank}A = \text{the number of nonzero singular values}.

The singular values also measure stretching. By the constrained extremes result from the last lesson applied to $\|A\mathbf{x}\|^2 = \mathbf{x}^T(A^TA)\mathbf{x}$ , the largest value of $\|A\mathbf{x}\|$ over unit vectors $\mathbf{x}$ is $\sigma_1$ , reached at $\mathbf{x} = \mathbf{v}_1$ , and the smallest is $\sigma_n$ .

The decomposition

Suppose $A$ has rank $r$ , so $\sigma_1, \ldots, \sigma_r$ are positive and the rest are $0$ . Normalize the orthogonal vectors $A\mathbf{v}_i$ :

\mathbf{u}_i = \frac{1}{\sigma_i}A\mathbf{v}_i \qquad (i = 1, \ldots, r).

These are orthonormal vectors in $\mathbb{R}^m$ . If $r < m$ , extend them to an orthonormal basis $\mathbf{u}_1, \ldots, \mathbf{u}_m$ of $\mathbb{R}^m$ . Since $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$ for every $i$ (both sides are $\mathbf{0}$ when $i > r$ ), putting these equations side by side gives $AV = U\Sigma$ , and multiplying on the right by $V^T = V^{-1}$ gives the theorem.

The singular value decomposition

Every $m \times n$ matrix $A$ of rank $r$ can be factored as

A = U\Sigma V^T,

where

$V$ is an $n \times n$ orthogonal matrix whose columns $\mathbf{v}_i$ (the right singular vectors) are an orthonormal eigenbasis of $A^TA$ ;
$\Sigma$ is the $m \times n$ matrix with $\sigma_1, \ldots, \sigma_r$ in the first $r$ diagonal positions and zeros everywhere else;
$U$ is an $m \times m$ orthogonal matrix whose first $r$ columns (the left singular vectors) are $\mathbf{u}_i = \frac{1}{\sigma_i}A\mathbf{v}_i$ .

Read right to left, $A\mathbf{x} = U\Sigma V^T\mathbf{x}$ says: rotate (or reflect) with $V^T$ , stretch along the coordinate axes by the singular values with $\Sigma$ , then rotate (or reflect) with $U$ . In particular, $A$ maps the unit circle to an ellipse whose semi-axes are $\sigma_1\mathbf{u}_1$ and $\sigma_2\mathbf{u}_2$ .

The recipe

Compute $A^TA$ and its eigenvalues. Order them from largest to smallest.
Find an orthonormal eigenvector $\mathbf{v}_i$ for each eigenvalue. These are the columns of $V$ .
The singular values are $\sigma_i = \sqrt{\lambda_i}$ . Build $\Sigma$ with the same shape as $A$ .
For each nonzero $\sigma_i$ , compute $\mathbf{u}_i = A\mathbf{v}_i / \sigma_i$ . If you need more columns for $U$ , complete to an orthonormal basis of $\mathbb{R}^m$ .

Worked example: A square matrix

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

A^TA = \begin{bmatrix} 3 & 4 \\ 0 & 5 \end{bmatrix}\begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}.

Its eigenvalues are $45$ (eigenvector $(1, 1)$ ) and $5$ (eigenvector $(-1, 1)$ ). So $\sigma_1 = \sqrt{45} = 3\sqrt{5}$ , $\sigma_2 = \sqrt{5}$ , and

\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1, 1), \qquad \mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(-1, 1).

Next, $A\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(3, 9)$ , so $\mathbf{u}_1 = \dfrac{1}{3\sqrt{5}} \cdot \tfrac{1}{\sqrt{2}}(3, 9) = \tfrac{1}{\sqrt{10}}(1, 3)$ . And $A\mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(-3, 1)$ , so $\mathbf{u}_2 = \tfrac{1}{\sqrt{10}}(-3, 1)$ . Therefore

A = \underbrace{\frac{1}{\sqrt{10}}\begin{bmatrix} 1 & -3 \\ 3 & 1 \end{bmatrix}}_{U}\underbrace{\begin{bmatrix} 3\sqrt{5} & 0 \\ 0 & \sqrt{5} \end{bmatrix}}_{\Sigma}\underbrace{\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}}_{V^T}.

Worked example: A wide matrix

Find an SVD of $A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}$ .

A^TA = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 1 \end{bmatrix}.

You can check that its eigenvalues are $3$ , $1$ and $0$ , with orthonormal eigenvectors

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

(For instance, $A^TA(1, 2, 1) = (3, 6, 3)$ .) The singular values are $\sqrt{3}$ , $1$ and $0$ , so $A$ has rank $2$ . Then $A\mathbf{v}_1 = \tfrac{1}{\sqrt{6}}(3, 3)$ , which divided by $\sqrt{3}$ gives $\mathbf{u}_1 = \tfrac{1}{\sqrt{2}}(1, 1)$ , and $A\mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(1, -1) = \mathbf{u}_2$ . Since $A$ is $2 \times 3$ , $\Sigma$ is $2 \times 3$ :

A = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\begin{bmatrix} \sqrt{3} & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} 1/\sqrt{6} & 2/\sqrt{6} & 1/\sqrt{6} \\ 1/\sqrt{2} & 0 & -1/\sqrt{2} \\ 1/\sqrt{3} & -1/\sqrt{3} & 1/\sqrt{3} \end{bmatrix}.

The vector $\mathbf{v}_3$ , which has singular value $0$ , spans $\operatorname{Nul}A$ .

Common mistake

Singular values are not the eigenvalues of $A$ . They are the square roots of the eigenvalues of $A^TA$ . For example, $\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$ has only the eigenvalue $0$ , but its singular values are $1$ and $0$ . The one exception: for a symmetric matrix, the singular values are the absolute values of the eigenvalues.

The SVD as a sum, and low-rank approximation

Multiplying out $U\Sigma V^T$ column-by-row gives the outer-product form

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

a sum of $r$ rank-one matrices, from most important to least. Keeping only the first $k$ terms gives a matrix $A_k$ of rank $k$ , and it can be proved that $A_k$ is the closest rank- $k$ matrix to $A$ . This is how the SVD compresses data: a $1000 \times 1000$ image stored as $k = 50$ terms needs about $50 \cdot 2001 \approx 100{,}000$ numbers instead of $1{,}000{,}000$ .

Worked example: A rank-one matrix

Find the singular values of $A = \begin{bmatrix} 2 & 2 \\ 1 & 1 \\ 2 & 2 \end{bmatrix}$ and write $A$ in outer-product form.

$A^TA = \begin{bmatrix} 9 & 9 \\ 9 & 9 \end{bmatrix}$ has eigenvalues $18$ and $0$ , with $\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1, 1)$ . So $\sigma_1 = \sqrt{18} = 3\sqrt{2}$ and $\sigma_2 = 0$ ; the rank is $1$ .

$A\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(4, 2, 4)$ , and dividing by $3\sqrt{2}$ gives $\mathbf{u}_1 = \tfrac{1}{3}(2, 1, 2)$ . Therefore

A = 3\sqrt{2}\,\mathbf{u}_1\mathbf{v}_1^T = 3\sqrt{2} \cdot \frac{1}{3}\begin{bmatrix} 2 \\ 1 \\ 2 \end{bmatrix}\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ 2 \end{bmatrix}\begin{bmatrix} 1 & 1 \end{bmatrix}.

For a full SVD, $U$ must be $3 \times 3$ : extend $\mathbf{u}_1$ with any orthonormal basis of the plane perpendicular to it, such as $\tfrac{1}{\sqrt{2}}(1, 0, -1)$ and $\tfrac{1}{3\sqrt{2}}(1, -4, 1)$ .

Tip

Useful checks: $\sigma_1^2 + \cdots + \sigma_n^2$ equals the sum of the squares of all entries of $A$ (it is the trace of $A^TA$ ). In the first example, $45 + 5 = 50 = 9 + 0 + 16 + 25$ .

Practice

Practice 1

Find the singular values of $A = \begin{bmatrix} 0 & -3 \\ 2 & 0 \end{bmatrix}$ .

Separate answers with commas, e.g. 2, -5

Practice 2

Find the largest singular value of $A = \begin{bmatrix} 4 & 0 \\ 3 & -5 \end{bmatrix}$ .