The Singular Value Decomposition

The Spectral Theorem factors a symmetric $n\times n$ matrix as $A=SDS^T$, where $D$ holds the eigenvalues $\lambda_i$ and the columns of $S$ are orthonormal eigenvectors, $Au_i=\lambda_i u_i$. A quiet but crucial consequence is that the image vectors $Au_1,\dots,Au_n$ are mutually orthogonal, with $\|Au_i\|=\|\lambda_i u_i\|=|\lambda_i|$. Finding an orthonormal basis of the domain whose images remain orthogonal is exactly the structure we want to keep — and the SVD shows it survives for any matrix $A$, even a non-square one. The bridge is the matrix $A^TA$: for an $n\times m$ matrix $A$ it is symmetric and $m\times m$, and by Lemma 9.3 its eigenvalues are nonnegative, since $A^TAv=\lambda v$ gives $\|Av\|^2=v^TA^TAv=\lambda\|v\|^2\ge 0$, forcing $\lambda\ge 0$. This lets us take square roots: the singular values of $A$ are $\sigma_i=\sqrt{\lambda_i}$ (Definition 9.2), listed in decreasing order $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_m\ge 0$. Theorem 9.2 then delivers the key fact: there is an orthonormal basis $v_1,\dots,v_m$ of $\mathbb{R}^m$ — an eigenbasis of $A^TA$ — for which the images $Av_1,\dots,Av_m$ are orthogonal with lengths $\|Av_i\|=\sigma_i$.

Package the basis of Theorem 9.2 into matrices. Let $V=[\,v_1\ \cdots\ v_m\,]$, an $m\times m$ orthogonal matrix whose columns are an orthonormal eigenbasis of $A^TA$. For each nonzero singular value set $u_i=\frac{1}{\sigma_i}Av_i,\qquad i=1,\dots,r,$ where $r=\operatorname{rank}(A)$; these are orthonormal (the $Av_i$ are orthogonal with length $\sigma_i$), and we complete them to an orthonormal basis $u_1,\dots,u_n$ of $\mathbb{R}^n$, giving an $n\times n$ orthogonal matrix $U=[\,u_1\ \cdots\ u_n\,]$. Since $Av_i=\sigma_i u_i$ for $i\le r$ and $Av_i=0$ otherwise, the relations collect into $AV=U\Sigma$; right-multiplying by $V^T=V^{-1}$ gives the Singular Value Decomposition (Theorem 9.3), $A=U\Sigma V^T.$ Here $\Sigma$ has the same shape as $A$ ($n\times m$): its first $r$ diagonal entries are $\sigma_1,\dots,\sigma_r>0$ and every other entry is $0$. Unlike diagonalization — which needs $A$ square, and symmetric to be orthogonal — the SVD exists for every matrix. By Proposition 9.3, the rank $r$ is exactly the number of nonzero singular values.

Multiplying out $A=U\Sigma V^T$ column by column turns the SVD into a sum of simple pieces (Remark 9.4): $A=\sigma_1 u_1 v_1^T+\sigma_2 u_2 v_2^T+\cdots+\sigma_r u_r v_r^T,$ where $u_i,v_i$ are the columns of $U,V$. Each outer product $u_i v_i^T$ is an $n\times m$ matrix of rank one — a single 'mode' of $A$ — and $\sigma_i$ weights how strongly that mode contributes. Because the weights are ordered $\sigma_1\ge\sigma_2\ge\cdots$, the leading terms carry most of $A$; keeping only the largest $k$ terms yields the best rank-$k$ approximation of $A$, the engine behind image compression, principal component analysis, and latent-factor models. Two norms read straight off the singular values: the operator (spectral) norm $\|A\|=\sigma_1$, the largest stretch factor, and the Frobenius norm $\|A\|_F=\sqrt{\sigma_1^2+\cdots+\sigma_r^2}$.

Read $A=U\Sigma V^T$ from right to left as three motions: $V^T$ rotates or reflects $\mathbb{R}^m$ (orthogonal maps preserve lengths and angles), $\Sigma$ stretches along the coordinate axes by the factors $\sigma_i$, and $U$ rotates or reflects the result inside $\mathbb{R}^n$. So $A$ carries the unit sphere of $\mathbb{R}^m$ to an ellipsoid in $\mathbb{R}^n$ whose semi-axes have lengths $\sigma_1,\dots,\sigma_r$ and point along the columns $u_1,\dots,u_r$ of $U$. When some $\sigma_i=0$ the ellipsoid is flattened into a lower dimension — in Example 9.1 the unit sphere of $\mathbb{R}^3$ maps onto a filled ellipse in $\mathbb{R}^2$ because $\sigma_3=0$ (Figure 9.1). The SVD also generalizes the Spectral Theorem: for a symmetric $A=SDS^T$ the singular values are the absolute eigenvalues $\sigma_i=|\lambda_i|$, and any negative sign of $\lambda_i$ is absorbed by flipping the matching singular vector, so $U$ and $V$ differ from $S$ only by signs. The SVD thus does for arbitrary matrices what orthogonal diagonalization does for symmetric ones.