The Singular Value Decomposition

The singular value decomposition, or SVD, is simply a way to break any matrix, even a non-square one, into three simple moves: a turn (or flip), a stretch along perpendicular axes, and another turn. "Decomposition" just means taking it apart into pieces, and the stretch factors are called singular values. The name fits nicely: a square matrix is singular (not invertible) exactly when one of its singular values is $0$, because then it squashes some direction flat. What it's good for: it tells you the most and least a matrix can stretch anything, and it's the engine behind image compression. All we're really saying here is that in $A = U\Sigma V^T$, $V^T$ picks out the input directions (the axes that get stretched), $\Sigma$ stretches along them by $\sigma_1 \ge \sigma_2 \ge \cdots$, and $U$ says where the stretched axes land. The stretch factors come from $\sigma_i = \sqrt{\lambda_i(A^TA)}$ (square roots of the eigenvalues of $A^TA$). Three moves, each of which you've met before; bear with it.

Take a look at the spectral theorem from earlier in this unit. Symmetric matrices get $A = PDP^T$: perpendicular axes, stretch, done. Most matrices aren't symmetric, and non-square ones can't even have eigenvalues. The SVD gives every matrix something almost as good, using two different orthogonal matrices instead of one.

Geometry. Any matrix sends the unit circle (sphere) to an ellipse (ellipsoid). The singular values are the lengths of its semi-axes; $V$'s columns are the input directions that map to those axes, and $U$'s columns are the axis directions. There's an animation further down that shows this for a $2\times2$ matrix.

Computing: the eigenvalues of the symmetric matrix $A^TA$ are $\sigma_i^2$; its eigenvectors are the columns of $V$; then $\vec u_i = \frac{1}{\sigma_i}A\vec v_i$. Think about why $A^TA$ is the right thing to look at. The squared length of $A\vec x$ is $\|A\vec x\|^2 = \vec x^TA^TA\vec x$, which is a quadratic form! From the last lesson, its largest value over unit vectors is the largest eigenvalue of $A^TA$. So the biggest stretch is $\sigma_1 = \sqrt{\lambda_1}$, and it happens along the top eigenvector $\vec v_1$.

Facts: the rank equals the number of nonzero singular values. Keeping only the largest $k$ terms of $A = \sum\sigma_i\vec u_i\vec v_i^T$ gives the best rank-$k$ approximation of $A$: that's compression.

A common mistake. It's tempting to think the singular values are just the eigenvalues of $A$, because both describe stretching. They aren't, in general. $\begin{bmatrix}1 & 1\\ 0 & 0\end{bmatrix}$ has eigenvalues $1$ and $0$ but singular values $\sqrt2$ and $0$. And singular values are never negative: $\begin{bmatrix}3 & 0\\ 0 & -2\end{bmatrix}$ has eigenvalue $-2$, but singular value $2$.

Image and video compression, recommender systems (the Netflix prize), noise reduction and latent semantic analysis of text are all built on the SVD.