Singular Value Decomposition (SVD) — full derivation

WHAT is SVD?

WHY does this differ from eigen-decomposition? Eigen-decomposition $A = P D P^{-1}$ only works for square matrices, and gives an orthogonal $P$ only when $A$ is symmetric. SVD works for every matrix, square or not, with two orthogonal bases (one for input space $\mathbb{R}^n$, one for output space $\mathbb{R}^m$).

HOW we derive it (from first principles)

The whole derivation rests on one safe object: $A^\top A$.

Step 1 — $A^\top A$ is symmetric and positive semi-definite

Symmetric: $(A^\top A)^\top = A^\top (A^\top)^\top = A^\top A$. ✓

PSD: for any $x$, $x^\top (A^\top A) x = (Ax)^\top(Ax) = \|Ax\|^2 \ge 0$. So every eigenvalue $\lambda_i \ge 0$. Define $\sigma_i := \sqrt{\lambda_i} \ge 0.$

Step 2 — Build $V$ from the eigenvectors of $A^\top A$

By the Spectral Theorem, choose orthonormal eigenvectors $v_1,\dots,v_n$: $A^\top A\, v_i = \lambda_i v_i = \sigma_i^2 v_i, \qquad v_i^\top v_j = \delta_{ij}.$ Order them so $\sigma_1 \ge \dots \ge \sigma_r > 0 = \sigma_{r+1}=\dots=\sigma_n$. Set $V = [\,v_1 \mid \dots \mid v_n\,]$. This is orthogonal: $V^\top V = I_n$. These are the right singular vectors.

Step 3 — Define $U$ so that $Av_i$ lines up

For $i \le r$ (where $\sigma_i > 0$) define $\boxed{\,u_i := \frac{1}{\sigma_i} A v_i\,}.$

WHY divide by $\sigma_i$? We want $u_i$ to be a unit vector. Check: $\|Av_i\|^2 = (Av_i)^\top(Av_i) = v_i^\top A^\top A\, v_i = v_i^\top(\sigma_i^2 v_i) = \sigma_i^2.$ So $\|Av_i\| = \sigma_i$, and dividing makes $\|u_i\| = 1$. ✓

Are the $u_i$ orthonormal? For $i\ne j$: $u_i^\top u_j = \frac{1}{\sigma_i\sigma_j}(Av_i)^\top(Av_j) = \frac{1}{\sigma_i\sigma_j} v_i^\top A^\top A v_j = \frac{\sigma_j^2}{\sigma_i\sigma_j} v_i^\top v_j = \frac{\sigma_j}{\sigma_i}\delta_{ij}=0.$ ✓

So $\{u_1,\dots,u_r\}$ is an orthonormal set in $\mathbb{R}^m$. Extend it to a full orthonormal basis $u_1,\dots,u_m$ (Gram–Schmidt on any completion). Set $U = [\,u_1\mid\dots\mid u_m\,]$.

Step 4 — Assemble and verify $A = U\Sigma V^\top$

We have, by construction, for all $i$: $A v_i = \sigma_i u_i \quad(\text{with } \sigma_i = 0 \text{ giving } Av_i = 0 \text{ for } i>r).$ Stack these as columns: $A[v_1\dots v_n] = [\sigma_1 u_1 \dots \sigma_n u_n]$, i.e. $A V = U \Sigma.$ Right-multiply by $V^\top$ (legal since $VV^\top = I_n$): $\boxed{A = U\Sigma V^\top}.$

The four fundamental subspaces (free bonus)

Worked Example 1 — a $2\times 2$ matrix

Let $A = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ (a $90°$ rotation).

Step A: form $A^\top A$. Why? It's our gateway. $A^\top A = \begin{pmatrix}0&-1\\1&0\end{pmatrix}\begin{pmatrix}0&1\\-1&0\end{pmatrix} = \begin{pmatrix}1&0\\0&1\end{pmatrix}=I.$ Step B: eigenvalues. $\lambda_1=\lambda_2=1 \Rightarrow \sigma_1=\sigma_2=1$. Why? A pure rotation stretches nothing — singular values $=1$ makes physical sense. Step C: any orthonormal $V$ works; take $V=I$, so $v_1=e_1, v_2=e_2$. Step D: $u_i = \tfrac1{\sigma_i}Av_i = Av_i$: $u_1 = Ae_1 = (0,-1)^\top$, $u_2 = Ae_2=(1,0)^\top$. So $U = \begin{pmatrix}0&1\\-1&0\end{pmatrix}$, $\Sigma=I$, $V^\top=I$, and indeed $U\Sigma V^\top = A$. ✓

Worked Example 2 — a rank-1, non-square matrix

Let $A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 0 \end{pmatrix}$ ($m=3,n=2$).

Step A: $A^\top A = \begin{pmatrix}2&2\\2&2\end{pmatrix}$. Why this step? Symmetric $2\times2$, easy eigenproblem. Step B: eigenvalues solve $\det(A^\top A - \lambda I)=0$: $(2-\lambda)^2-4=0 \Rightarrow \lambda(\lambda-4)=0$. So $\lambda_1=4,\lambda_2=0$, giving $\sigma_1=2,\sigma_2=0$. Rank $r=1$. Why one zero? Rows are identical → rank 1. Step C: eigenvector for $\lambda_1=4$: $v_1=\tfrac1{\sqrt2}(1,1)^\top$. For $\lambda_2=0$: $v_2=\tfrac1{\sqrt2}(1,-1)^\top$. Step D: $u_1 = \tfrac1{\sigma_1}Av_1 = \tfrac12 A\cdot\tfrac1{\sqrt2}(1,1)^\top = \tfrac1{2\sqrt2}(2,2,0)^\top = \tfrac1{\sqrt2}(1,1,0)^\top$. Why? Confirms $\|u_1\|=1$. Extend to $u_2 = \tfrac1{\sqrt2}(1,-1,0)^\top$, $u_3=(0,0,1)^\top$ to complete the basis. $A = U\begin{pmatrix}2&0\\0&0\\0&0\end{pmatrix}V^\top,\quad U=\begin{pmatrix}\tfrac1{\sqrt2}&\tfrac1{\sqrt2}&0\\ \tfrac1{\sqrt2}&-\tfrac1{\sqrt2}&0\\0&0&1\end{pmatrix}.$

Common Mistakes (Steel-manned)

Flashcards

Connections

• Spectral Theorem — the symmetric eigen-decomposition that powers Step 1–2.
• Eigenvalues and Eigenvectors — singular values are $\sqrt{\text{eigenvalues of } A^\top A}$.
• Four Fundamental Subspaces — $u_i,v_i$ give orthonormal bases for all four.
• Positive Semi-Definite Matrices — guarantees $\lambda_i \ge 0$.
• Low-Rank Approximation / Principal Component Analysis (PCA) — truncated SVD applications.
• Moore-Penrose Pseudoinverse — $A^+ = V\Sigma^+ U^\top$.
• Gram-Schmidt Process — used to extend $u_i$ to a full basis.

Concept Map

Hinglish (regional understanding)