Singular Value Decomposition (SVD)
Definition and Concept
For any real $m \times n$ matrix $A$, there exist orthogonal matrices $U \in \mathbb{R}^{m \times m}$ and $V \in \mathbb{R}^{n \times n}$, and a diagonal matrix $\Sigma \in \mathbb{R}^{m \times n}$ such that: \[ A = U \Sigma V^T \] where
Columns of $U$ are called left singular vectors.
Columns of $V$ are called right singular vectors.
Diagonal entries $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r \ge 0$ of $\Sigma$ are called singular values of $A$, where $r = \text{rank}(A)$.
SVD works for any matrix, regardless of shape — square, rectangular, invertible, or singular. It decomposes $A$ into a rotation, followed by a scaling, followed by another rotation. This is what makes SVD more general than eigen-decomposition, which is only defined for square matrices.
SVD reveals the underlying structure of a matrix while filtering out noise. This is why it is widely used in compression, recommender systems, and dimensionality reduction.
Consider a table of movie ratings by users, where rows represent users and columns represent movies:
\[ A = \begin{bmatrix} 5 & 1 & 5 \\ 1 & 5 & 1 \\ 4 & 1 & 4 \\ 1 & 4 & 2 \end{bmatrix} \quad \begin{array}{l} \text{(rows: Ann, Bob, Cid, Dee)} \\ \text{(columns: Titanic, Rambo, Notebook)} \end{array} \]
Ann and Cid both rate Titanic and Notebook highly while rating Rambo low; Bob shows the opposite pattern. SVD decomposes $A$ as $A = U\Sigma V^T$, where $U \in \mathbb{R}^{4\times 2}$, $\Sigma \in \mathbb{R}^{2\times 2}$, and $V^T \in \mathbb{R}^{2\times 3}$, automatically discovering this “Action vs.\ Romance” pattern purely from the numbers, without ever being told what a genre is.
Reading the Axes: $U$, $\Sigma$, and $V$
An axis in this context is a direction that SVD discovers in the data, not something labeled in advance. Every user (or movie) is assigned a number along this axis, called its projection. The sign of the number indicates which side of the axis an item falls on, and the magnitude indicates how strongly it leans that way.
$U$ is an orthogonal matrix: its columns form an orthonormal set (mutually perpendicular, unit length). Each column of $U$ represents one preference direction across users.
Sign indicates direction (e.g., negative $\to$ romance side, positive $\to$ action side).
Magnitude indicates strength of that preference.
Continuing the movie ratings example, the first column of $U$ (the dominant genre axis) might be: \[ U_{:,1} = \begin{pmatrix} -0.60 \\ +0.53 \\ -0.48 \\ +0.35 \end{pmatrix} \quad \text{(Ann, Bob, Cid, Dee)} \] Ann's value of $-0.60$ places her strongly on the romance side, consistent with her ratings $(5,1,5)$. Bob's $+0.53$ places him on the action side, consistent with $(1,5,1)$.
$\Sigma$ is diagonal, with non-negative entries arranged in descending order: $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$.
A large $\sigma_i$ means the corresponding pattern explains a lot of the variance in the data.
A small $\sigma_i$ means the pattern contributes little — often just noise.
In practice, only the top few singular values are retained, since they capture most of the structure using far fewer dimensions.
For the movie ratings matrix, suppose $\sigma_1 = 10.8$ and $\sigma_2 = 3.4$ (with $\sigma_3 \approx 0$). Since $\sigma_1$ is over three times larger than $\sigma_2$, the Action-vs-Romance split accounts for most of why ratings vary between users. Keeping only $\sigma_1$ still reconstructs most of the original ratings — this is the basis of dimensionality reduction.
$V$ is also an orthogonal matrix, with orthonormal columns. Each column of $V$ represents a distinct latent theme direction for the movies (columns of $A$), rather than the users. A movie's coordinate along an axis shows how strongly it aligns with that theme: a high positive value indicates strong association with one extreme (e.g., action), while a large negative value indicates the opposite extreme (e.g., romance).
Continuing the example, the first column of $V$ might be: \[ V_{:,1} = \begin{pmatrix} -0.58 \\ +0.60 \\ -0.55 \end{pmatrix} \quad \text{(Titanic, Rambo, Notebook)} \] Rambo's $+0.60$ places it firmly on the action side. Titanic and Notebook both score negative, placing them on the romance side. This axis is the romance-vs-action split, discovered purely from ratings with no genre label ever supplied to the algorithm.
Orthogonality
A set of vectors $\{v_1, v_2, \dots\}$ is orthonormal if it satisfies two conditions simultaneously:
Orthogonal: every pair is perpendicular, $v_i \cdot v_j = 0$ for $i \ne j$.
Normalized: every vector has unit length, $\|v_i\| = 1$.
The columns of $U$ and the columns of $V$ are always orthonormal sets. Geometrically, in three dimensions, this means three mutually perpendicular unit vectors — like the $x$, $y$, $z$ axes of a coordinate system, but oriented in whatever direction best captures the data's structure.
Eigenvalues, Eigenvectors, and the Origin of SVD
When a matrix transforms a vector, the result is usually rotated, stretched, and mixed all at once. However, every matrix has special directions — called eigenvectors — along which the transformation acts simply: the vector is only stretched or shrunk, never redirected. The scale factor along that direction is the eigenvalue $\lambda$.
A large eigenvalue means the matrix strongly amplifies data along that direction; a small or near-zero eigenvalue means that direction is barely affected or flattened entirely.
SVD is built directly on this idea, generalized to matrices that are not necessarily square:
$V$ consists of the eigenvectors of $A^TA$.
$U$ consists of the eigenvectors of $AA^T$.
$\sigma_i = \sqrt{\lambda_i}$, where $\lambda_i$ are the (shared, non-zero) eigenvalues of $A^TA$ and $AA^T$.
This is what allows SVD to work even on rectangular matrices, where ordinary eigenvalues are not defined.
A matrix is called singular if it is not invertible. If any singular value $\sigma_i = 0$, the matrix collapses (squashes to zero) along that direction — this is exactly the condition under which the matrix is singular. The term “singular value” is named after this connection.
Computing the SVD
Given $A \in \mathbb{R}^{m\times n}$, the SVD is computed as follows:
Compute $A^TA$, an $n \times n$ symmetric matrix.
Find the eigenvalues $\lambda_i$ of $A^TA$; these give $\sigma_i^2 = \lambda_i$.
Find the eigenvectors of $A^TA$, and normalize them to unit length — these become the columns of $V$.
Set $\sigma_i = \sqrt{\lambda_i}$, sorted from largest to smallest, and place them along the diagonal of $\Sigma$.
Compute $u_i = \dfrac{1}{\sigma_i}Av_i$ for each non-zero $\sigma_i$, and normalize — these become the columns of $U$.
Eigenvectors obtained by solving $(A^TA - \lambda I)v = 0$ are not automatically unit length; always divide by $\|v\|$ before placing a vector into $V$ or $U$.
Compute the SVD of \[ A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \\ 0 & 0 \end{bmatrix}. \]
Step 1. Compute $A^TA$: \[ A^TA = \begin{bmatrix} 9+1 & 3+3 \\ 3+3 & 1+9 \end{bmatrix} = \begin{bmatrix} 10 & 6 \\ 6 & 10 \end{bmatrix}. \]
Step 2. Find the eigenvalues. Solving $\det(A^TA - \lambda I) = 0$: \[ (10-\lambda)^2 - 36 = 0 \implies 10 - \lambda = \pm 6 \implies \lambda_1 = 16,\ \lambda_2 = 4. \]
Step 3. Find and normalize the eigenvectors. For $\lambda_1 = 16$: solving $(A^TA - 16I)v = 0$ gives $v_1 = (1,1)$, normalized to $\frac{1}{\sqrt2}(1,1)$. For $\lambda_2 = 4$: $v_2 = (1,-1)$, normalized to $\frac{1}{\sqrt2}(1,-1)$. Hence \[ V = \frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}. \]
Step 4. Singular values: \[ \sigma_1 = \sqrt{16} = 4, \qquad \sigma_2 = \sqrt{4} = 2, \qquad \Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ 0 & 0 \end{bmatrix}. \]
Step 5. Compute $U$: \[ u_1 = \frac{1}{\sigma_1}Av_1 = \frac{1}{4}\cdot\frac{1}{\sqrt2}(4,4,0) = \frac{1}{\sqrt2}(1,1,0), \] \[ u_2 = \frac{1}{\sigma_2}Av_2 = \frac{1}{2}\cdot\frac{1}{\sqrt2}(2,-2,0) = \frac{1}{\sqrt2}(1,-1,0). \] Since $U$ must be $3\times 3$ and orthogonal, the third column $u_3$ is any unit vector orthogonal to $u_1$ and $u_2$; here $u_3 = (0,0,1)$ works directly.
Result: \[ U = \begin{bmatrix} 1/\sqrt2 & 1/\sqrt2 & 0 \\ 1/\sqrt2 & -1/\sqrt2 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \qquad \Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ 0 & 0 \end{bmatrix}, \qquad V = \frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}. \] One can verify by direct multiplication that $U\Sigma V^T = A$.
Low-Rank Approximation
Every matrix $A$ can be written as a sum of rank-1 pieces: \[ A = \sum_{i=1}^{r} \sigma_i\, u_i v_i^T, \] where $r = \text{rank}(A)$. Since $\sigma_1 \ge \sigma_2 \ge \dots$, the earlier terms in this sum capture the most important structure in $A$. The best rank-$k$ approximation of $A$, for $k < r$, is obtained by keeping only the first $k$ terms: \[ A_k = \sum_{i=1}^{k} \sigma_i\, u_i v_i^T. \] Discarding the terms with small singular values loses very little information, since those terms correspond to weak or noisy patterns in the data.
For $A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}$, suppose $\sigma_1 = \sqrt3$, $u_1 = \frac{1}{\sqrt6}(1,2,1)$, and $v_1 = \frac{1}{\sqrt2}(1,1)$. The rank-1 approximation is: \[ A_1 = \sigma_1\, u_1 v_1^T = \begin{bmatrix} 1/\sqrt6 \\ 2/\sqrt6 \\ 1/\sqrt6 \end{bmatrix} \begin{bmatrix}\sqrt3\end{bmatrix} \begin{bmatrix} 1/\sqrt2 & 1/\sqrt2 \end{bmatrix} = \begin{bmatrix} 0.5 & 0.5 \\ 1.0 & 1.0 \\ 0.5 & 0.5 \end{bmatrix}. \] Comparing $A_1$ to the original $A = \begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}$: every row of $A_1$ is a scalar multiple of a single vector, confirming $\text{rank}(A_1)=1$, and $A_1$ captures the dominant structure of $A$ using only one term instead of two.
Shortcut Rules for Special Matrices
For any real $m\times n$ matrix $A$: \[ A = U\Sigma V^T, \qquad \sigma_i = \sqrt{\lambda_i(A^TA)} = \sqrt{\lambda_i(AA^T)}. \] The singular values are sorted $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$, where $r = \text{rank}(A)$.
For $A = \begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}$: $A^TA = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ has eigenvalues $3, 1$, so $\sigma_1 = \sqrt3$ and $\sigma_2 = 1$. Since $\text{rank}(A) = 2$, there are exactly two non-zero singular values.
Let $A = A^T$ with eigenvalues $\lambda_i$.
Rule A (Positive Semi-Definite, $\lambda_i \ge 0$ for all $i$): \[ \sigma_i = \lambda_i(A), \qquad \sum_i \sigma_i = \sum_i \lambda_i = \text{Trace}(A). \]
Rule B (General Symmetric Matrix): \[ \sigma_i = |\lambda_i(A)|. \] Rule A is a special case of Rule B; use Rule B whenever any eigenvalue could be negative.
Let $A = \begin{bmatrix}4&0\\0&9\end{bmatrix}$. Since $A$ is symmetric with eigenvalues $4, 9$ (both $\ge 0$), Rule A applies directly: $\sigma_1 + \sigma_2 = 4 + 9 = 13$.
Let $A = \begin{bmatrix}-5&0\\0&2\end{bmatrix}$. $A$ is symmetric, but its eigenvalues $-5, 2$ are not both non-negative, so Rule A does not apply; Rule B must be used instead: \[ \sigma_1 + \sigma_2 = |-5| + |2| = 5 + 2 = 7. \] Note that this differs from simply summing the eigenvalues, which would incorrectly give $-3$.
For vectors $u \in \mathbb{R}^m$, $v \in \mathbb{R}^n$:
Case 1 — $A = uv^T$ (general rank-1): $\text{rank}(A) = 1$, so only $\sigma_1$ is non-zero: \[ \sigma_1 = \|u\|_2 \cdot \|v\|_2 = \sqrt{\textstyle\sum u_i^2}\cdot\sqrt{\textstyle\sum v_i^2}. \]
Case 2 — $M = uu^T$ (symmetric rank-1): again only $\sigma_1$ is non-zero: \[ \sigma_1 = \|u\|_2^2 = u^Tu = \text{Trace}(M). \]
Let $u = (1,2)$, $v = (3,4)$, and $A = uv^T$. Then $\|u\|_2 = \sqrt5$ and $\|v\|_2 = \sqrt{25} = 5$, so \[ \sigma_1 = \sqrt5 \cdot 5 = 5\sqrt5. \]
Let $u = (1,2,2)$, and let $M = uu^T$ be the resulting $3\times 3$ rank-1 matrix. Then \[ \sigma_1 = u^Tu = 1 + 4 + 4 = 9 = \text{Trace}(M). \]
Applications
Solving linear systems: $Ax = b$, including least squares for rank-deficient matrices.
Low-rank approximation in data compression.
Computing pseudoinverse: \[ A^+ = V \Sigma^+ U^T \] where $\Sigma^+$ is obtained by taking reciprocal of non-zero singular values.
Principal Component Analysis (PCA).