Singular value decomposition

Measure the directions a matrix stretches, build its singular value decomposition, and use the same factors to find the closest fit with the shortest coefficient vector.

How much can a matrix stretch a unit input?

A matrix can stretch different directions by different amounts. Take the real matrix $A=\begin{bmatrix}4&3\\-3&-4\end{bmatrix}$. It sends a column $x=(x_1,x_2)^T$ to $(4x_1+3x_2,-3x_1-4x_2)^T$. Compare inputs of length one, so a larger output reflects the direction chosen rather than a larger starting input. Here length means the Euclidean norm $\|x\|=\sqrt{x_1^2+x_2^2}$.

To find the largest output length, first square it. Squaring a nonnegative length preserves its order. Transpose, written T above a matrix, exchanges its rows and columns. The identity $\|y\|^2=y^Ty$ turns the length calculation into a symmetric matrix problem:

$$\begin{aligned}\|Ax\|^2&=(Ax)^T(Ax)=x^T(A^TA)x,\\G=A^TA&=\begin{bmatrix}4&-3\\3&-4\end{bmatrix}\begin{bmatrix}4&3\\-3&-4\end{bmatrix}=\begin{bmatrix}25&24\\24&25\end{bmatrix}.\end{aligned}$$

The Gram matrix G records dot products of the columns of A. It controls squared output length.

For any real matrix A, its Gram matrix is symmetric and satisfies $x^TGx=\|Ax\|^2\ge0$ for every x. This property is called positive semidefiniteness. If $Gv=\lambda v$ for a unit eigenvector v, then $\lambda=v^TGv=\|Av\|^2\ge0$. Thus its eigenvalues are squared lengths; their nonnegative square roots are the singular values.

Find the two stretches

  1. For this G, $\det(G-\lambda I)=(25-\lambda)^2-24^2=(\lambda-49)(\lambda-1)$. The eigenvalues are 49 and 1. Their unit eigenvectors are $v_1=(1,1)^T/\sqrt2$ and $v_2=(1,-1)^T/\sqrt2$: multiplication by G gives 49v₁ and v₂ respectively.
  2. They are perpendicular, so every unit input has the form $x=c_1v_1+c_2v_2$ with $c_1^2+c_2^2=1$. Substituting gives $\|Ax\|^2=49c_1^2+c_2^2=1+48c_1^2$. This ranges from 1 to 49. The largest length is 7, attained at ±v₁; the smallest is 1, attained at ±v₂.
  3. The singular values are therefore $\sigma_1=7$ and $\sigma_2=1$. Directly, $Av_1=7(1,-1)^T/\sqrt2$ and $Av_2=(1,1)^T/\sqrt2$. The v vectors are input directions; their images point in different output directions.

The same reasoning works for an $m\times n$ matrix, mapping n input coordinates to m output coordinates. A symmetric Gram matrix has an orthonormal eigenbasis. In that basis, squared output length is a sum $\sum_i\lambda_i c_i^2$. On unit inputs, the weights $c_i^2$ add to one. This proves the largest stretch is $\sqrt{\lambda_1}$. Restricting the input to directions perpendicular to v₁ leaves the next largest stretch $\sqrt{\lambda_2}$; continuing gives the remaining directions, including zero stretches.

We report $p=\min(m,n)$ singular values, in nonincreasing order and with repetitions: $\sigma_1\ge\cdots\ge\sigma_p\ge0$. The n-by-n matrix $A^TA$ has n eigenvalues. When n>m, its extra n−p eigenvalues are zero; they describe additional input directions killed by A. You may also meet a convention listing all n square roots, padded with these zeros. We use the p-entry convention throughout. The rank is the number of positive values, counted with multiplicity.

A rectangular map can erase a direction

  1. The map $B=\begin{bmatrix}2&0&0\\0&1&0\end{bmatrix}$ sends $(x_1,x_2,x_3)^T$ to $(2x_1,x_2)^T$. Its Gram matrix is diag(4,1,0), while its two listed singular values are 2 and 1. The unit input e₃ maps to zero, so the smallest length over all unit inputs is 0, not the smallest listed value 1.
  2. The unit sphere consists of inputs with $x_1^2+x_2^2+x_3^2=1$. Its images fill the ellipse $y_1^2/4+y_2^2\le1$: choose $x_3=\pm\sqrt{1-y_1^2/4-y_2^2}$. By contrast, our invertible square A maps its unit circle to an ellipse boundary. A unit ball, defined by $\|x\|\le1$, always maps to a filled ellipsoid, possibly flattened into a smaller subspace.