Singular Value Decomposition (SVD) intuition and computation

WHAT is SVD?

WHY does this always exist (unlike eigendecomposition, which needs a square, diagonalizable matrix)? Because we build it from $A^\top A$ and $AA^\top$, which are always symmetric and positive semidefinite, so they always have a full set of orthonormal eigenvectors with non-negative eigenvalues.

HOW to derive it from scratch

We want orthonormal directions that $A$ maps to orthogonal directions.

Step 1 — Look at $A^\top A$. It is symmetric ($(A^\top A)^\top = A^\top A$) and PSD ($x^\top A^\top A x = \|Ax\|^2 \ge 0$). By the spectral theorem it has orthonormal eigenvectors $v_1,\dots,v_n$ with eigenvalues $\lambda_i \ge 0$: $A^\top A\, v_i = \lambda_i v_i.$

Why this step? Symmetric PSD ⇒ guaranteed orthonormal eigenbasis and non-negative eigenvalues — exactly the raw materials we need.

Step 2 — Define singular values. $\sigma_i = \sqrt{\lambda_i}\ \ge 0.$

Why? $\lambda_i = \|Av_i\|^2$ (see below), so $\sigma_i = \|Av_i\|$ — a length, hence non-negative. This is where the "stretch factor" lives.

Check: $\|Av_i\|^2 = (Av_i)^\top(Av_i) = v_i^\top A^\top A v_i = v_i^\top \lambda_i v_i = \lambda_i.$

Step 3 — Define left singular vectors. For $\sigma_i > 0$ set $u_i = \frac{1}{\sigma_i} A v_i.$

Why? This normalizes $Av_i$ to unit length. And they come out orthonormal: $u_i^\top u_j = \frac{1}{\sigma_i\sigma_j} v_i^\top A^\top A v_j = \frac{\lambda_j}{\sigma_i\sigma_j} v_i^\top v_j = \delta_{ij}.$

Step 4 — Reassemble. $Av_i = \sigma_i u_i$ for every $i$ means, stacking columns, $A V = U\Sigma \quad\Rightarrow\quad A = U\Sigma V^\top$ (using $V^{-1}=V^\top$ since $V$ is orthogonal). ∎

Dual coding: the unit circle (right singular vectors $v_i$) → mapped by $A$ → an ellipse whose axes are $\sigma_i u_i$.

Geometric reading (the picture)

$A = U\Sigma V^\top$ acts on a vector $x$ right-to-left:

1. $V^\top$ rotates $x$ to align with the singular directions.
2. $\Sigma$ stretches axis $i$ by factor $\sigma_i$ (turns the sphere into an ellipsoid).
3. $U$ rotates the result into the output space.

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

Let $A=\begin{pmatrix}3 & 0\\ 0 & -2\end{pmatrix}$.

Step 1: $A^\top A = \begin{pmatrix}9&0\\0&4\end{pmatrix}$. Why? We always start from $A^\top A$. Step 2: eigenvalues $9,4$ ⇒ $\sigma_1=3,\ \sigma_2=2$, with $v_1=e_1, v_2=e_2$. Step 3: $u_1=\frac1{3}Av_1=(1,0)$, $u_2=\frac1{2}Av_2=(0,-1)$. Why the sign? $Av_2=(0,-2)$, so normalizing flips it — SVD absorbs the sign into $U$, keeping $\sigma>0$. Result: $U=\begin{pmatrix}1&0\\0&-1\end{pmatrix},\ \Sigma=\begin{pmatrix}3&0\\0&2\end{pmatrix},\ V=I$.

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

Let $A=\begin{pmatrix}1&1\\1&1\\1&1\end{pmatrix}$ ($3\times 2$).

Step 1: $A^\top A=\begin{pmatrix}3&3\\3&3\end{pmatrix}$. Why? Column-column dot products. Step 2: eigenvalues of $\begin{pmatrix}3&3\\3&3\end{pmatrix}$ are $6$ and $0$ ⇒ $\sigma_1=\sqrt6,\ \sigma_2=0$. Rank 1! Eigenvector for $6$: $v_1=\frac1{\sqrt2}(1,1)$. Step 3: $u_1=\frac1{\sqrt6}Av_1=\frac1{\sqrt6}\cdot\frac1{\sqrt2}(2,2,2)=\frac1{\sqrt3}(1,1,1)$. Why? $Av_1=\frac1{\sqrt2}(2,2,2)$; dividing by $\sigma_1=\sqrt6$ gives a unit vector. Result: $A=\sqrt6\,u_1 v_1^\top$ — a single rank-1 term, as expected.

The 80/20: what SVD is FOR

Common mistakes (steel-manned)

Active recall

Flashcards

Connections

• Eigenvalues and Eigenvectors — SVD is built from eigenpairs of $A^\top A$.
• Spectral Theorem — guarantees the orthonormal eigenbasis SVD relies on.
• Principal Component Analysis (PCA) — direct application of $V$ and $\sigma_i^2$.
• Orthogonal Matrices — why $U,V$ preserve length (pure rotations/reflections).
• Matrix Norms — $\|A\|_2=\sigma_1$, $\|A\|_F=\sqrt{\sum\sigma_i^2}$.
• Pseudoinverse (Moore–Penrose) — $A^+ = V\Sigma^+U^\top$.
• Rank of a Matrix — rank = number of nonzero singular values.

Concept Map

Hinglish (regional understanding)