Singular value decomposition

Ketan Suhaas Saichandran

linear-algebraeigenvaluessvdmatrix-factorization

Statement

Every $A\in\mathbb{R}^{m\times n}$, square or not, defective or not, factors as:

$$ A = U\Sigma V^T, \quad U \in \mathbb{R}^{m\times m}, V \in \mathbb{R}^{n\times n} \text{ orthogonal}, \ \Sigma \in \mathbb{R}^{m\times n} \text{ diagonal}, \ \sigma_1\geq\sigma_2\geq\cdots\geq0. $$

Shapes

For a tall $A$ ($m>n$), the $m\times n$ matrix $\Sigma$ is a square diagonal block with zero rows underneath; for a wide $A$ ($m<n$) it has zero columns to the right:

$$ \underbrace{A}_{m\times n}=\underbrace{U}_{m\times m}\ \underbrace{\begin{pmatrix}\sigma_1&&\\&\ddots&\\&&\sigma_n\\\hline0&\cdots&0\\\vdots&&\vdots\\0&\cdots&0\end{pmatrix}}_{\Sigma,\ m\times n}\ \underbrace{V^T}_{n\times n} \qquad\text{(tall)}, $$

$$ \underbrace{A}_{m\times n}=\underbrace{U}_{m\times m}\ \underbrace{\begin{pmatrix}\sigma_1&&&0&\cdots&0\\&\ddots&&\vdots&&\vdots\\&&\sigma_m&0&\cdots&0\end{pmatrix}}_{\Sigma,\ m\times n}\ \underbrace{V^T}_{n\times n} \qquad\text{(wide)}. $$

The zero rows or columns of $\Sigma$ multiply the extra columns of $U$ or $V$ by $0$, so only the first $r=\operatorname{rank}(A)$ columns of each ever matter. Dropping them gives the compact ("thin") form:

$$ \underbrace{A}_{m\times n}=\underbrace{U_r}_{m\times r}\ \underbrace{\Sigma_r}_{r\times r}\ \underbrace{V_r^T}_{r\times n}. $$

Intuition: SVD finds one orthonormal basis for the input space and another for the output space, in which $A$ is just a (rectangular) diagonal scaling.

$A$ sends the orthonormal basis $v_1,v_2$ to the (generally differently oriented) orthogonal directions $\sigma_1u_1,\sigma_2u_2$: a unit circle always lands as an ellipse.

Construction

$A^TA$ ($n\times n$) and $AA^T$ ($m\times m$) are always symmetric and positive semidefinite, even when $A$ itself is rectangular or far from symmetric, so the spectral theorem always applies to them:

$$ A^TA = V\Lambda V^T, \quad AA^T = U\Lambda' U^T, \quad \lambda_i = \sigma_i^2 \ \text{(shared nonzero eigenvalues)}. $$

Shapes

$$ \underbrace{A^TA}_{n\times n}=\underbrace{V}_{n\times n}\ \underbrace{\Lambda}_{n\times n}\ \underbrace{V^T}_{n\times n}, \qquad \underbrace{AA^T}_{m\times m}=\underbrace{U}_{m\times m}\ \underbrace{\Lambda'}_{m\times m}\ \underbrace{U^T}_{m\times m}. $$

Intuition: $A^TA$ and $AA^T$ are always square, even when $A$ itself is rectangular, which is exactly why the spectral theorem can always be applied to them.

The columns of $V$ and $U$ are linked by $Av_i = \sigma_iu_i$ for every $\sigma_i>0$.

Intuition: $A^TA$ and $AA^T$ are always symmetric, so they're never defective, giving SVD for literally any matrix.

Example

Reusing the wide $A=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$ (from Fundamental subspaces):

$$ AA^T = \begin{pmatrix}2&1\\1&2\end{pmatrix}, \ \text{eigenvalues } 3,1, \ \text{eigenvectors } u_1=\tfrac{1}{\sqrt2}(1,1), \ u_2=\tfrac{1}{\sqrt2}(1,-1). $$

So $\sigma_1=\sqrt3, \sigma_2=1$. Then $v_1 = A^Tu_1/\sigma_1 = \tfrac{1}{\sqrt6}(1,1,2)$, and checking the link:

$$ Av_1 = \tfrac{1}{\sqrt6}\begin{pmatrix}3\\3\end{pmatrix} = \sqrt3\cdot\tfrac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix} = \sigma_1u_1. \ \checkmark $$

Rank and the fundamental subspaces

$\operatorname{rank}(A)$ is the count of nonzero singular values. The columns of $U$ and $V$ split exactly along the four fundamental subspaces from before:

$u_1,\dots,u_r$ span $C(A)$; the rest of $U$ spans $N(A^T)$
$v_1,\dots,v_r$ span $C(A^T)$; the rest of $V$ spans $N(A)$

Intuition: SVD hands you a ready-made orthonormal basis for every one of the four fundamental subspaces.

Example

Here $r=2=m$, so $u_1,u_2$ span all of $C(A)=\mathbb{R}^2$ and $N(A^T)=\{0\}$. The leftover $v_3=\tfrac{1}{\sqrt3}(-1,-1,1)$ spans $N(A)$, matching the earlier post exactly.

Low-rank approximation

Expanding $U\Sigma V^T$ column by column gives a rank-1 sum, largest singular value first:

$$ A = \sum_i \sigma_iu_iv_i^T. $$

Shapes

$$ \underbrace{A}_{m\times n}=\sum_i\underbrace{\sigma_iu_i}_{m\times1}\ \underbrace{v_i^T}_{1\times n}. $$

Intuition: each term pairs one output direction ($u_i$) with one input direction ($v_i$), scaled by how much $A$ cares about that pairing ($\sigma_i$); summing them, biggest first, rebuilds $A$ exactly.

Keeping only the top $k$ terms gives the best possible rank-$k$ approximation to $A$ (Eckart-Young).

Intuition: dropping the smallest singular values keeps the directions $A$ cares about most and discards the least important ones.

Summing the rank-one terms from biggest singular value to smallest rebuilds $A$ exactly; stopping early gives the best rank-$k$ approximation.

The pseudoinverse

Inverting only the nonzero singular values gives the Moore-Penrose pseudoinverse:

$$ A^+ = V\Sigma^+U^T, \quad \Sigma^+_{ii} = 1/\sigma_i \ (\sigma_i\neq0), \ 0 \ \text{otherwise}. $$

$x^+=A^+b$ is exactly the minimum-norm solution to $Ax=b$, the $x_{\text{row}}$ from The big picture.

Intuition: where $A$ can't be inverted, the pseudoinverse does the best it can, landing exactly in the row space.

Shapes

$A$ maps $\mathbb{R}^n\to\mathbb{R}^m$, so $A^+$ goes back, $\mathbb{R}^m\to\mathbb{R}^n$, and $\Sigma^+$ is the transpose-shaped $\Sigma$ with each nonzero $\sigma_i$ inverted:

$$ \underbrace{A^+}_{n\times m}=\underbrace{V}_{n\times n}\ \underbrace{\Sigma^+}_{n\times m}\ \underbrace{U^T}_{m\times m}, \qquad \underbrace{x^+}_{n\times1}=\underbrace{A^+}_{n\times m}\underbrace{b}_{m\times1}. $$