Exercises — Singular Value Decomposition (SVD) — full derivation

$U$ acts on the output space ${\mathbb{R}}^m={\mathbb{R}}^4$, so $U$ is $4\times 4$. $V$ acts on the input space ${\mathbb{R}}^n={\mathbb{R}}^7$, so $V$ is $7\times 7$. $\Sigma$ must map ${\mathbb{R}}^7\to {\mathbb{R}}^4$ so the product $U\Sigma V^{\top }$ is $4\times 7$ — so $\Sigma$ is $\boxed{4\times 7}$. Answer: $U$ is $4\times 4$, $\Sigma$ is $4\times 7$, $V$ is $7\times 7$.

Singular values are ${\sigma }_i=\sqrt{{\lambda }_i}$ where ${\lambda }_i$ are eigenvalues of $A^{\top }A$ (never of $A$). $\sqrt{25}=5,\sqrt{9}=3,\sqrt{0}=0$. Ordered: ${\sigma }_1=5,{\sigma }_2=3,{\sigma }_3=0$. Rank $r$ = number of strictly positive singular values $=\boxed{2}$.

The null space of $A$ is $\{x:Ax=0\}$. From the derivation, $A{v}_i={\sigma }_i{u}_i$, so $A{v}_i=0$ exactly when ${\sigma }_i=0$. Here ${\sigma }_3={\sigma }_4=0$, so $\boxed{v_3,v_4}$ span the null space.

Step A — form $A^{\top }A$ (our safe gateway): $A^{\top }A=\left(\begin{array}{cc}3& 0\\ 0& -2\end{array}\right)\left(\begin{array}{cc}3& 0\\ 0& -2\end{array}\right)=\left(\begin{array}{cc}9& 0\\ 0& 4\end{array}\right).$ Step B — eigenvalues: already diagonal, so ${\lambda }_1=9,{\lambda }_2=4$, giving ${\sigma }_1=3,{\sigma }_2=2$ (ordered largest first). Step C — right singular vectors (eigenvectors of $A^{\top }A$): $v_1=(1,0{)}^{\top }$ (for $\lambda =9$), $v_2=(0,1{)}^{\top }$ (for $\lambda =4$). So $V=I$. Step D — left singular vectors via $u_i=\frac{1}{{\sigma }_i}A{v}_i$ (this locks in the sign): $u_1=\frac{1}{3}A(1,0{)}^{\top }=\frac{1}{3}(3,0{)}^{\top }=(1,0{)}^{\top }.$ $u_2=\frac{1}{2}A(0,1{)}^{\top }=\frac{1}{2}(0,-2{)}^{\top }=(0,-1{)}^{\top }.$ So $U=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right),\Sigma =\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right),V=I.$ Check: $U\Sigma V^{\top }=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right)=\left(\begin{array}{cc}3& 0\\ 0& -2\end{array}\right)=A.$ ✓ Notice the minus sign got absorbed into $U$ — singular values stay positive.

$A^{\top }A=\left(\begin{array}{cc}4& 0\\ 0& 9\end{array}\right)$, eigenvalues $9,4$, so ${\sigma }_1=3,{\sigma }_2=2$. The largest singular value is $3$, matching the $2\text{nd}$ axis, so we must reorder so $v_1$ points along $e_2$: $v_1=(0,1{)}^{\top },v_2=(1,0{)}^{\top }$, giving $V=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$. $u_1=\frac{1}{3}A(0,1{)}^{\top }=\frac{1}{3}(0,3{)}^{\top }=(0,1{)}^{\top };u_2=\frac{1}{2}A(1,0{)}^{\top }=(1,0{)}^{\top }.$ $U=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\Sigma =\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right).$ Check: $U\Sigma V^{\top }=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}2& 0\\ 0& 3\end{array}\right)$. ✓

Here $m=1,n=2$. Form $A^{\top }A$ (the $n\times n$ route is $2\times 2$): $A^{\top }A=\left(\begin{array}{c}3\\ 4\end{array}\right)\left(\begin{array}{cc}3& 4\end{array}\right)=\left(\begin{array}{cc}9& 12\\ 12& 16\end{array}\right).$ Eigenvalues solve ${\lambda }^2-(9+16)\lambda +(9\cdot 16-12^2)=0\Rightarrow {\lambda }^2-25\lambda +0=0$, so $\lambda =25$ or $0$. ${\sigma }_1=\sqrt{25}=5$, and ${\sigma }_2=0$ (but $\Sigma$ is $1\times 2$, so it only holds one diagonal entry: $\Sigma =\left(\begin{array}{cc}5& 0\end{array}\right)$). Sanity check: for a single row, the only singular value equals the length of that row: $\sqrt{3^2+4^2}=5$. ✓

Step A: $A^{\top }A=\left(\begin{array}{ccc}1& 2& 0\\ 2& 4& 0\end{array}\right)\left(\begin{array}{cc}1& 2\\ 2& 4\\ 0& 0\end{array}\right)=\left(\begin{array}{cc}5& 10\\ 10& 20\end{array}\right).$ Step B — eigenvalues: $\det (A^{\top }A-\lambda I)=(5-\lambda )(20-\lambda )-100={\lambda }^2-25\lambda =0$, so ${\lambda }_1=25,{\lambda }_2=0$. Thus ${\sigma }_1=5,{\sigma }_2=0$, and rank $r=1$ (the rows/columns are proportional). Step C — right singular vectors: ${\lambda }_1=25$: solve $(A^{\top }A-25I)v=0\Rightarrow \left(\begin{array}{cc}-20& 10\\ 10& -5\end{array}\right)v=0\Rightarrow v_1\propto (1,2{)}^{\top }$, normalised $v_1=\frac{1}{\sqrt{5}}(1,2{)}^{\top }$. ${\lambda }_2=0$: $v_2\perp v_1$, so $v_2=\frac{1}{\sqrt{5}}(2,-1{)}^{\top }$. Step D — left singular vectors: $u_1=\frac{1}{5}A{v}_1=\frac{1}{5}\cdot \frac{1}{\sqrt{5}}A(1,2{)}^{\top }=\frac{1}{5\sqrt{5}}(5,10,0{)}^{\top }=\frac{1}{\sqrt{5}}(1,2,0{)}^{\top }.$ Check $\Vert u_1\Vert =\frac{1}{\sqrt{5}}\sqrt{1+4}=1$. ✓ Extend $\{u_1\}$ to an orthonormal basis of ${\mathbb{R}}^3$ (e.g. via Gram-Schmidt Process): $u_2=\frac{1}{\sqrt{5}}(2,-1,0{)}^{\top },u_3=(0,0,1{)}^{\top }$. $U=\left(\begin{array}{ccc}\frac{1}{\sqrt{5}}& \frac{2}{\sqrt{5}}& 0\\ \frac{2}{\sqrt{5}}& -\frac{1}{\sqrt{5}}& 0\\ 0& 0& 1\end{array}\right),\Sigma =\left(\begin{array}{cc}5& 0\\ 0& 0\\ 0& 0\end{array}\right),V=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}1& 2\\ 2& -1\end{array}\right).$

With rank $r=1$, split the singular vectors at index $r$ (see Four Fundamental Subspaces):

• Column space ($\text{col}(A)\subset {\mathbb{R}}^3$) $=\text{span}\{u_1\}=\left\{\frac{1}{\sqrt{5}}(1,2,0{)}^{\top }\right\}$.
• Left null space ($\text{null}(A^{\top })$) $=\text{span}\{u_2,u_3\}=\left\{\frac{1}{\sqrt{5}}(2,-1,0{)}^{\top },(0,0,1{)}^{\top }\right\}$.
• Row space ($\text{col}(A^{\top })\subset {\mathbb{R}}^2$) $=\text{span}\{v_1\}=\left\{\frac{1}{\sqrt{5}}(1,2{)}^{\top }\right\}$.
• Null space ($\text{null}(A)$) $=\text{span}\{v_2\}=\left\{\frac{1}{\sqrt{5}}(2,-1{)}^{\top }\right\}$. Notice column space ⟂ left null space in ${\mathbb{R}}^3$, and row space ⟂ null space in ${\mathbb{R}}^2$ — SVD hands you the orthogonal splitting for free.

Direct sum of squares: $1^2+2^2+2^2+4^2+0+0=1+4+4+16=25$. Singular-value side: ${\sigma }_1^2+{\sigma }_2^2=25+0=25$. Equal. ✓ Why this always holds: $U$ and $V^{\top }$ are rotations/reflections, which never change lengths, so the total squared "size" of $A$ is stored entirely in $\Sigma$, i.e. in the ${\sigma }_i^2$.

The Eckart–Young theorem says the best rank-$k$ approximation (in Frobenius norm) is $A_k={\sum }_{i=1}^k{\sigma }_i{u}_i{v}_i^{\top }$. Here $k=1$: $A_1={\sigma }_1{u}_1{v}_1^{\top }=5\cdot \frac{1}{\sqrt{5}}\left(\begin{array}{c}1\\ 2\\ 0\end{array}\right)\cdot \frac{1}{\sqrt{5}}\left(\begin{array}{cc}1& 2\end{array}\right)=\frac{5}{5}\left(\begin{array}{c}1\\ 2\\ 0\end{array}\right)\left(\begin{array}{cc}1& 2\end{array}\right)=\left(\begin{array}{cc}1& 2\\ 2& 4\\ 0& 0\end{array}\right)=A.$ Why exact? $A$ already has rank $1$ (${\sigma }_2=0$), so its rank-1 approximation loses nothing. The approximation error equals $\sqrt{{\sum }_{i>k}{\sigma }_i^2}=\sqrt{0}=0$.

$\Sigma =\left(\begin{array}{cc}5& 0\\ 0& 0\\ 0& 0\end{array}\right)$ is $3\times 2$. Invert nonzero entries and transpose to $2\times 3$: ${\Sigma }^{+}=\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ 0& 0& 0\end{array}\right).$ Then $A^{+}=V{\Sigma }^{+}{U}^{\top }$. Multiply: $V{\Sigma }^{+}=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}1& 2\\ 2& -1\end{array}\right)\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ 0& 0& 0\end{array}\right)=\frac{1}{\sqrt{5}}\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ \frac{2}{5}& 0& 0\end{array}\right).$ $U^{\top }$ has first row $\frac{1}{\sqrt{5}}(1,2,0)$. Multiplying: $A^{+}=\frac{1}{\sqrt{5}}\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ \frac{2}{5}& 0& 0\end{array}\right)U^{\top }=\frac{1}{25}\left(\begin{array}{ccc}1& 2& 0\\ 2& 4& 0\end{array}\right).$ Check $A{A}^{+}A=A$: since $A^{+}$ is the "undo where possible" map, applying $A$, then $A^{+}$, then $A$ returns $A$. (Verified numerically in the checks below.)

The covariance-like matrix is $X^{\top }X$ (up to a factor $\frac{1}{N-1}$). Its eigenvectors are exactly the $v_i$ — the principal component directions. Its eigenvalues are ${\sigma }_i^2$. So:

• $v_i$ = the $i$-th principal axis (the direction of the $i$-th most spread in the data).
• $\frac{{\sigma }_i^2}{N-1}$ = the variance of the data projected onto $v_i$.
• The fraction of total variance captured by the first $k$ components is $\frac{{\sum }_{i\le k}{\sigma }_i^2}{{\sum }_i{\sigma }_i^2}$. This is why SVD of the data matrix is PCA — no covariance matrix needs to be formed explicitly (and it is numerically safer not to).

Start from $A=U\Sigma V^{\top }$. Transpose both sides (using $(XY{)}^{\top }=Y^{\top }{X}^{\top }$ and $(\Sigma {)}^{\top }={\Sigma }^{\top }$): $A^{\top }=(U\Sigma V^{\top }{)}^{\top }=V{\Sigma }^{\top }{U}^{\top }.$ This is a valid SVD of $A^{\top }$: $V$ and $U$ are orthogonal, and ${\Sigma }^{\top }$ is the (transposed-shape) diagonal matrix carrying the same diagonal entries ${\sigma }_i$. Because singular values are uniquely determined by the matrix, the nonzero diagonal entries of ${\Sigma }^{\top }$ — which equal those of $\Sigma$ — are the singular values of $A^{\top }$. Hence $A$ and $A^{\top }$ share the same nonzero singular values. $■$ (The roles of left/right singular vectors simply swap.)

Write any unit vector in the $v$-basis: $x={\sum }_i{c}_i{v}_i$ with ${\sum }_i{c}_i^2=1$ (since the $v_i$ are orthonormal, $\Vert x{\Vert }^2=\sum c_i^2$). Apply $A$ using $A{v}_i={\sigma }_i{u}_i$: $Ax={\sum }_i{c}_i{\sigma }_i{u}_i.$ The $u_i$ are orthonormal, so $\Vert Ax{\Vert }^2={\sum }_i{c}_i^2{\sigma }_i^2.$ Since ${\sigma }_1\ge {\sigma }_i$ for all $i$: $\Vert Ax{\Vert }^2={\sum }_i{c}_i^2{\sigma }_i^2\le {\sigma }_1^2{\sum }_i{c}_i^2={\sigma }_1^2.$ So $\Vert Ax\Vert \le {\sigma }_1$ for every unit $x$, and the bound is hit by $x=v_1$ (then $c_1=1$, rest $0$, giving $\Vert A{v}_1\Vert ={\sigma }_1$). Therefore ${\max }_{\Vert x\Vert =1}\Vert Ax\Vert ={\sigma }_1$. $■$

By the Spectral Theorem, $S=Q\Lambda Q^{\top }$ with $Q$ orthogonal and $\Lambda =\text{diag}({\lambda }_i)$. Compute $S^{\top }S=S^2$ (since $S=S^{\top }$): $S^{\top }S=Q\Lambda Q^{\top }Q\Lambda Q^{\top }=Q{\Lambda }^2{Q}^{\top },$ using $Q^{\top }Q=I$. So $S^{\top }S$ has eigenvalues ${\lambda }_i^2$. Singular values: ${\sigma }_i=\sqrt{{\lambda }_i^2}=|{\lambda }_i|$. $■$ When do they coincide? ${\sigma }_i={\lambda }_i$ exactly when ${\lambda }_i\ge 0$ for all $i$ — i.e. when $S$ is positive semi-definite. If any eigenvalue is negative, its singular value flips sign and the corresponding singular vector absorbs a $-1$ (into $u_i$, as we saw in L2.1).

Take determinants of $A=U\Sigma V^{\top }$. Determinant is multiplicative: $\det (XY)=\det X\det Y$. $\det A=\det U\cdot \det \Sigma \cdot \det V^{\top }.$ $U,V$ orthogonal $\Rightarrow \det U,\det V^{\top }\in \{+1,-1\}$ (rotations give $+1$, reflections $-1$). $\det \Sigma ={\prod }_i{\sigma }_i$ (product of the diagonal). Taking absolute values kills the $\pm 1$: $|\det A|=|\det U||\det \Sigma ||\det V^{\top }|=1\cdot ({\prod }_i{\sigma }_i)\cdot 1={\prod }_{i=1}^n{\sigma }_i.■$ Geometry: $|\det A|$ is the factor by which $A$ scales volumes. Rotations/reflections ($U,V$) preserve volume; only the stretches ${\sigma }_i$ change it. So the volume scaling is the product of the stretches — exactly $\prod {\sigma }_i$. If any ${\sigma }_i=0$, the volume collapses and $\det A=0$.