Singular Value Decomposition

The final and best factorization

This is the lecture on the singular value decomposition — “but everybody calls it the SVD.” Strang announces it as “the final and best factorization of a matrix”: the factors will be orthogonal matrix, diagonal matrix, orthogonal matrix,

$$A = U \Sigma V^T.$$

These are things we’ve seen before — the special good matrices, orthogonal and diagonal. The new point is that we need two orthogonal matrices, probably different ones. And $A$ can be any matrix whatsoever: every matrix has this factorization. Strang calls it “maybe the bringing together of everything in this course.”

One family we just studied fits instantly: symmetric positive definite matrices. There the eigenvectors are orthogonal, so the usual eigenvector matrix $S$ becomes an especially good $Q$, and positive definiteness makes $\Lambda$ positive:

$$A = Q \Lambda Q^T \qquad \text{(symmetric positive definite case)}.$$

That is an SVD — orthogonal, diagonal, orthogonal — with the same $Q$ on both sides. But in general the eigenvector matrix isn’t orthogonal, so eigenvectors alone won’t do. In general we need a $U$ and a separate $V$.

The goal: an orthogonal basis that stays orthogonal

Remember the picture of a linear transformation — the most important figure in the course. A typical vector $\mathbf{v}_1$ in the row space gets taken over to some vector $\mathbf{u}_1 = A\mathbf{v}_1$ in the column space. What the SVD looks for is very special: an orthogonal basis in the row space that gets knocked over into an orthogonal basis in the column space.

Finding some orthogonal basis of the row space is no big deal — start with any old basis and grind through Gram–Schmidt. But if you take any old orthogonal basis, there is no reason its images under $A$ should be orthogonal. The SVD asks for the special setup where they are.

While we’re at it, make everything orthonormal. Then $A\mathbf{v}_1$ won’t be a unit vector, only a multiple of one — and that stretching number is no longer called $\lambda$; it’s called $\sigma$:

$$A\mathbf{v}_1 = \sigma_1 \mathbf{u}_1, \quad A\mathbf{v}_2 = \sigma_2 \mathbf{u}_2, \quad \ldots, \quad A\mathbf{v}_r = \sigma_r \mathbf{u}_r,$$

where $r$ is the rank. What about the null spaces? No problem. Complete $\mathbf{v}_1, \ldots, \mathbf{v}_r$ with a basis $\mathbf{v}_{r+1}, \ldots, \mathbf{v}_n$ of the null space, and complete the $\mathbf{u}$‘s to an orthonormal basis of all of $\mathbb{R}^m$ — those extra directions just produce zeroes on the diagonal of $\Sigma$.

Now the usual step: think of what you want, then express it as a matrix multiplication. Column by column, the equations $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$ say

$$A V = U \Sigma,$$

and since $V$ is a square orthogonal matrix, $V^{-1} = V^T$:

Making the U’s disappear: the great matrix A^T A

Here’s the problem: two orthogonal matrices, and we don’t want to find them both at once. Strang wants to “cook up some expression that will make the $U$‘s disappear.” It’s the same combination that keeps showing up for a general rectangular matrix — $A^TA$, “that’s the great matrix”: symmetric, and positive definite or at least positive semidefinite. Compute it from the factorization:

$$A^TA = \left(V\Sigma^T U^T\right)\left(U \Sigma V^T\right) = V\, \Sigma^T\Sigma\, V^T = V \begin{bmatrix} \sigma_1^2 & & \\ & \sigma_2^2 & \\ & & \ddots \end{bmatrix} V^T.$$

The key point: $U^TU$ collapses into $I$, and the $U$‘s are out of the picture. What’s left is a perfect $Q\Lambda Q^T$ for the symmetric positive (semi)definite matrix $A^TA$. So we can read everything off:

$A$ itself is nothing special — but $A^TA$ is special, and its eigenvalues are positive (or zero) exactly because it’s positive (semi)definite. That’s why the square roots make sense.

Example 1: an invertible 2 by 2 — and an honest slip

Take $A = \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix}$. It’s invertible, rank two, and not symmetric — so its eigenvectors are no help; they’re not orthogonal. First step: compute $A^TA$.

$$A^TA = \begin{bmatrix} 4 & -3 \\ 4 & 3 \end{bmatrix}\begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix} = \begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix}.$$

It better come out symmetric — and it does. Its eigenvectors are the familiar pair $(1,1)$ and $(1,-1)$: multiplying by $(1,1)$ gives $(32, 32)$, so $\lambda_1 = 32$; multiplying by $(1,-1)$ gives $18$ times $(1,-1)$, so $\lambda_2 = 18$. Normalize (divide by $\sqrt{2}$; the $32$ and $18$ don’t change), and we have

$$V = \frac{1}{\sqrt 2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \qquad \Sigma = \begin{bmatrix} \sqrt{32} & 0 \\ 0 & \sqrt{18} \end{bmatrix}.$$

For the $\mathbf{u}$‘s, go the $AA^T$ way:

$$AA^T = \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix}\begin{bmatrix} 4 & -3 \\ 4 & 3 \end{bmatrix} = \begin{bmatrix} 32 & 0 \\ 0 & 18 \end{bmatrix}.$$

A lucky accident — it comes out diagonal, so its eigenvectors are as nice as can be: $(1,0)$ and $(0,1)$, “the best orthogonal matrix, just the identity.” And the eigenvalues are $32$ and $18$ again. Are we surprised?

Now check the product $U\Sigma V^T$ against $A$. The first row works perfectly: $\sqrt{32}/\sqrt{2} = \sqrt{16} = 4$, giving $4$ and $4$. The second row: $\sqrt{18}/\sqrt{2} = \sqrt{9} = 3$ — but it produces $3, -3$ where $A$ has $-3, 3$. “Phooey.” Strang stops, genuinely puzzled: “It shouldn’t have happened, but it did.” The catch — which he leaves as “a very important reason to come back on Wednesday” — is that eigenvectors of $AA^T$ only determine each $\mathbf{u}_i$ up to sign, and the signs must be matched to the $\mathbf{v}$‘s. The safe rule is to take $\mathbf{u}_i = A\mathbf{v}_i / \sigma_i$: here $A\mathbf{v}_2 = (0, -3\sqrt 2)$, so $\mathbf{u}_2 = (0, -1)$, not $(0, 1)$, and everything comes out right while $\Sigma$ keeps its positive diagonal.

Here is that whole example as a picture. $A$ sends the unit circle to an ellipse; the dashed input directions are $\mathbf{v}_1, \mathbf{v}_2$, and their images are exactly the ellipse’s axes, $\sigma_1\mathbf{u}_1$ and $\sigma_2\mathbf{u}_2$:

Example 2: a singular matrix, rank one

Second example, where the matrix is singular: $A = \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}$, rank one. Now the picture becomes easy, because the row space and column space are just lines. The row space is all multiples of $(4,3)$; the null space is the perpendicular line. The columns are all multiples of $(4,8)$ — that is, of $(1,2)$ — so the column space is that line, and the null space of $A^T$ is perpendicular to it.

Choosing orthonormal bases here is no problem — each space is one-dimensional, so just make unit vectors:

$$\mathbf{v}_1 = \begin{bmatrix} 0.8 \\ 0.6 \end{bmatrix}, \qquad \mathbf{u}_1 = \frac{1}{\sqrt 5}\begin{bmatrix} 1 \\ 2 \end{bmatrix}.$$

For $\sigma_1$, go back to where the sigmas come from:

Complete the bases with the null space directions: $\mathbf{v}_2 = (0.6, -0.8)$ perpendicular to $\mathbf{v}_1$, and $\mathbf{u}_2 = \tfrac{1}{\sqrt 5}(2, -1)$. Altogether,

$$\begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix} = \underbrace{\frac{1}{\sqrt 5}\begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}}_{U} \underbrace{\begin{bmatrix} \sqrt{125} & 0 \\ 0 & 0 \end{bmatrix}}_{\Sigma} \underbrace{\begin{bmatrix} 0.8 & 0.6 \\ 0.6 & -0.8 \end{bmatrix}}_{V^T}.$$

Do the multiplication and pray it comes out right: $\sqrt 5$ cancels into $\sqrt{125}$ leaving $\sqrt{25} = 5$, five multiplies the unit-vector entries into whole numbers, and out comes $A$. The null space vectors $\mathbf{v}_2$ and $\mathbf{u}_2$ were multiplied by that zero — easy to deal with. The key ones are the ones in the row space and column space: columns times diagonal times rows, coming together to produce $A$.

The right bases for the four subspaces

Step back and see what we’re really doing: choosing the right basis for the four subspaces of linear algebra.

• $\mathbf{v}_1, \ldots, \mathbf{v}_r$: an orthonormal basis for the row space, dimension $r$.
• $\mathbf{u}_1, \ldots, \mathbf{u}_r$: an orthonormal basis for the column space, dimension $r$.
• $\mathbf{v}_{r+1}, \ldots, \mathbf{v}_n$: an orthonormal basis for the null space, dimension $n - r$.
• $\mathbf{u}_{r+1}, \ldots, \mathbf{u}_m$: an orthonormal basis for the null space of $A^T$, dimension $m - r$.

Strang stops there — the SVD could be developed further, and it returns in the very last lectures of the course.

Problems

Work these with the recipe from the lecture: $A^TA$ for the $\mathbf{v}$‘s and $\sigma$‘s, then $\mathbf{u}_i = A\mathbf{v}_i/\sigma_i$.

Problem 29.1 Full SVD, invertible case

Find the singular value decomposition of

$$A = \begin{bmatrix} 2 & 2 \\ -1 & 1 \end{bmatrix}.$$

Show solution

Compute $A^TA = \begin{bmatrix} 5 & 3 \\ 3 & 5 \end{bmatrix}$. Its eigenvectors are $(1,1)$ with eigenvalue $8$ and $(1,-1)$ with eigenvalue $2$. So

$$V = \frac{1}{\sqrt 2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \qquad \Sigma = \begin{bmatrix} \sqrt 8 & 0 \\ 0 & \sqrt 2 \end{bmatrix} = \begin{bmatrix} 2\sqrt 2 & 0 \\ 0 & \sqrt 2 \end{bmatrix}.$$

Now the safe rule for the $\mathbf{u}$‘s: $A\mathbf{v}_1 = \tfrac{1}{\sqrt 2}(4, 0) = (2\sqrt 2, 0)$, so $\mathbf{u}_1 = A\mathbf{v}_1/\sigma_1 = (1, 0)$. And $A\mathbf{v}_2 = \tfrac{1}{\sqrt 2}(0, -2) = (0, -\sqrt 2)$, so $\mathbf{u}_2 = (0, -1)$ — note the minus sign that the eigenvectors of $AA^T$ alone would not have decided. Then

$$A = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} 2\sqrt 2 & 0 \\ 0 & \sqrt 2 \end{bmatrix} \frac{1}{\sqrt 2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},$$

and multiplying it out recovers $A$: first row $2\sqrt 2/\sqrt 2 = 2$ twice; second row $-\sqrt 2/\sqrt 2 = -1$ and $+1$.

Problem 29.2 Rank-one SVD

Find the SVD of the rank-one matrix

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

Identify which columns of $V$ and $U$ are bases for the row space, column space, null space, and null space of $A^T$.

Show solution

The row space is the line of multiples of $(3,4)$; the column space is the line of multiples of $(1,1)$. Unit vectors: $\mathbf{v}_1 = (0.6, 0.8)$ and $\mathbf{u}_1 = \tfrac{1}{\sqrt 2}(1,1)$.

For $\sigma_1$: $A^TA = \begin{bmatrix} 18 & 24 \\ 24 & 32 \end{bmatrix}$ has rank one, so one eigenvalue is $0$ and the other is the trace, $50$. Thus $\sigma_1 = \sqrt{50} = 5\sqrt 2$. Check: $A\mathbf{v}_1 = (1.8 + 3.2,\ 1.8 + 3.2) = (5, 5) = 5\sqrt 2 \cdot \tfrac{1}{\sqrt 2}(1,1)$. Correct.

Complete the bases with the perpendicular directions: $\mathbf{v}_2 = (0.8, -0.6)$ spans the null space, $\mathbf{u}_2 = \tfrac{1}{\sqrt 2}(1, -1)$ spans the null space of $A^T$. Then

$$A = \frac{1}{\sqrt 2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 5\sqrt 2 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 0.6 & 0.8 \\ 0.8 & -0.6 \end{bmatrix}.$$

Column 1 of $V$: row space. Column 1 of $U$: column space. Column 2 of $V$: null space. Column 2 of $U$: left null space. The zero in $\Sigma$ wipes out the null space directions.

Problem 29.3 Symmetric positive definite case

Let $A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$. Find its SVD, and explain why in this case one orthogonal matrix serves as both $U$ and $V$.

Show solution

$A$ is symmetric positive definite: its eigenvalues are $3$ (eigenvector $(1,1)$) and $1$ (eigenvector $(1,-1)$) — both positive. Because $A$ is symmetric, the eigenvectors are orthogonal, so the eigenvector matrix can be taken orthogonal:

$$Q = \frac{1}{\sqrt 2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \qquad A = Q \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix} Q^T.$$

This is already orthogonal times diagonal times orthogonal with a positive diagonal, so it is the SVD, with $U = V = Q$ and $\sigma_1 = 3$, $\sigma_2 = 1$. Consistency check via the recipe: $A^TA = A^2$ has eigenvalues $9$ and $1$, whose positive square roots are $3$ and $1$ — the singular values of a symmetric positive definite matrix are exactly its eigenvalues.

Problem 29.4 Shared eigenvalues, quick reasoning

(a) Without computing them, explain why $A^TA$ and $AA^T$ always have the same nonzero eigenvalues. (b) What are the singular values of an orthogonal matrix $Q$?

Show solution

(a) The eigenvalues of $AB$ are the same as the eigenvalues of $BA$ — eigenvalues don’t change when the order of multiplication is switched. Take $B = A^T$: then $A^TA$ and $AA^T$ share their nonzero eigenvalues, which are the $\sigma_i^2$ of the SVD. (Directly: if $A^TA\mathbf{v} = \lambda\mathbf{v}$ with $\lambda \neq 0$, multiply by $A$ to get $AA^T(A\mathbf{v}) = \lambda(A\mathbf{v})$, and $A\mathbf{v} \neq \mathbf{0}$ since $\lambda \neq 0$.)

(b) For an orthogonal matrix, $Q^TQ = I$, whose eigenvalues are all $1$. The singular values are the positive square roots, so every $\sigma_i = 1$. An orthogonal matrix stretches nothing — its SVD is $Q = Q \cdot I \cdot I^T$.