Singular Value Decomposition

Observation

A non square matrix has no eigenvalues

If $A \in \mathcal{M}_{m\times n}$ with $m \neq n$, the equation $Ax = \lambda x$ makes no sense: $Ax$ lives in $\mathbb{R}^m$ while $x$ lives in $\mathbb{R}^n$. However, two square matrices can always be built from $A$, and both are symmetric.

$A^\top A \in \mathcal{M}_{n\times n} \qquad AA^\top \in \mathcal{M}_{m\times m}$

Symmetric$(A^\top A)^\top = A^\top (A^\top)^\top = A^\top A$, and the same for $AA^\top$

Same eigenvalues$A^\top A$ and $AA^\top$ share their nonzero eigenvalues; the larger one carries extra copies of $0$

Recall

Spectral theorem for symmetric matrices

Every symmetric matrix $S \in \mathcal{M}_{n\times n}$ satisfies these properties, which is what makes the SVD possible.

a$S$ has $n$ real eigenvalues, accounting for multiplicities

beach eigenspace has dimension equal to the multiplicity of its $\lambda$

ceigenvectors of different eigenvalues are orthogonal

d$S$ is orthogonally diagonalizable: $S = PDP^\top$ with $P^{-1} = P^\top$

Definition

Singular values of a matrix

The singular values of $A \in \mathcal{M}_{m\times n}$ are the square roots of the eigenvalues of $A^\top A$. By convention, they are written in decreasing order.

$\sigma_i = \sqrt{\lambda_i}, \qquad \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0$

Theorem

Singular value decomposition

Any $A \in \mathcal{M}_{m\times n}$ of rank $r$ factors as $A = U\Sigma V^\top$, with $U, V$ orthogonal and $\Sigma$ diagonal. The columns of $V$ and $U$ are built from orthonormal eigenvectors, stacked side by side:

$V = \begin{pmatrix} \uparrow & \uparrow & & \uparrow \\ v_1 & v_2 & \cdots & v_n \\ \downarrow & \downarrow & & \downarrow \end{pmatrix} \qquad U = \begin{pmatrix} \uparrow & \uparrow & & \uparrow \\ u_1 & u_2 & \cdots & u_m \\ \downarrow & \downarrow & & \downarrow \end{pmatrix}$

$\Sigma = \begin{pmatrix} \sigma_1 & & & \\ & \ddots & & 0\\ & & \sigma_r & \\ & 0 & & 0 \end{pmatrix}$

Method

From A to U, Σ, V

Given $A \in \mathcal{M}_{m\times n}$ with $\operatorname{rank} A = r \le \min(m,n)$, we look for $A = U\Sigma V^\top$ with $U = (u_1, \dots, u_m)$ and $V = (v_1, \dots, v_n)$.

Eigenvalues. Find the eigenvalues $\lambda_i$ of $A^\top A$ (or of $AA^\top$, whichever is smaller) from the characteristic equation $\det(A^\top A - \lambda I) = 0$.

Eigenspaces. For each $\lambda_i$, solve $(A^\top A - \lambda_i I)x = 0$ to get its eigenspace.

Orthonormalize. If an eigenspace has dimension $1$, just normalize its eigenvector. If it has dimension $>1$ and the basis found isn't already orthogonal, run Gram-Schmidt on it first, then normalize.

Build $\Sigma$ and $V$. Set $\sigma_i = \sqrt{\lambda_i}$ on the diagonal of $\Sigma$, and place the orthonormal eigenvectors as columns of $V$, both in decreasing order of $\lambda_i$.

Build $U$. For $i \le r$, $\sigma_i \neq 0$ and $u_i = \dfrac{1}{\sigma_i} Av_i$. If $U$ needs more columns ($m > r$), complete it with an orthonormal basis of $N(A^\top)$.

Be careful with the order of vectors: each singular vector must sit in the column matching its singular value in $\Sigma$.

Example

Setting up the problem

We compute the singular value decomposition of the matrix below. Since $A \in \mathcal{M}_{4\times 3}$, we will get $U \in \mathcal{M}_{4\times 4}$, $\Sigma \in \mathcal{M}_{4\times 3}$ and $V \in \mathcal{M}_{3\times 3}$.

$A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$

Step 1

Eigenvalues of $A^\top A$

Compute $A^\top A = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}$.

The characteristic equation is $\det(A^\top A - \lambda I) = -(\lambda-4)(\lambda-1)^2 = 0$.

The eigenvalues are $\lambda_1 = 4$, with multiplicity $1$, and $\lambda_2 = 1$, with multiplicity $2$.

Step 2

Eigenspace of each eigenvalue

For $\lambda_1 = 4$: solving $(A^\top A - 4I)x = 0$ gives $x=y=z$, a line spanned by $w_1 = (1,1,1)^\top$.

For $\lambda_2 = 1$: solving $(A^\top A - I)x = 0$ leaves a single equation $x+y+z=0$, a plane of dimension $2$.

Taking $y,z$ free, a basis of this plane is $w_2 = (-1,1,0)^\top$, $w_3 = (-1,0,1)^\top$. But $w_2\cdot w_3 = 1 \neq 0$: not orthogonal.

Step 3

Gram-Schmidt on the plane

Keep $\bar w_2 = w_2 = (-1,1,0)^\top$.

$\bar w_3 = w_3 - \dfrac{w_3\cdot \bar w_2}{\bar w_2\cdot \bar w_2}\bar w_2 = \left(-\tfrac12,-\tfrac12,1\right)^\top$

Check: $\bar w_2\cdot \bar w_3 = \tfrac12-\tfrac12+0=0$. Orthogonal basis found.

Normalize: $v_2 = \dfrac{1}{\sqrt2}(-1,1,0)^\top$, $v_3 = \dfrac{1}{\sqrt6}(-1,-1,2)^\top$. Also $v_1 = \dfrac{1}{\sqrt3}(1,1,1)^\top$.

Step 4

Σ and V

$\sigma_1 = \sqrt4 = 2$, $\sigma_2 = \sigma_3 = \sqrt1 = 1$, so $\Sigma = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$.

Placing $v_1, v_2, v_3$ as columns, in decreasing order of $\lambda_i$: $V = \begin{pmatrix} 1/\sqrt3 & -1/\sqrt2 & -1/\sqrt6 \\ 1/\sqrt3 & 1/\sqrt2 & -1/\sqrt6 \\ 1/\sqrt3 & 0 & 2/\sqrt6 \end{pmatrix}$.

Step 5

Building U

Here $r=3 < m=4$: three columns come from $u_i = \dfrac{1}{\sigma_i}Av_i$, and $U$ needs one more from $N(A^\top)$.

$Av_1 = \dfrac{1}{\sqrt3}(3,1,1,1)^\top$, so $u_1 = \dfrac12\cdot\dfrac{1}{\sqrt3}(3,1,1,1)^\top = \left(\dfrac{\sqrt3}{2},\dfrac{\sqrt3}{6},\dfrac{\sqrt3}{6},\dfrac{\sqrt3}{6}\right)^\top$.

$Av_2 = \dfrac{1}{\sqrt2}(0,-1,1,0)^\top$ and $Av_3 = \dfrac{1}{\sqrt6}(0,-1,-1,2)^\top$, so $u_2 = \left(0,-\dfrac{1}{\sqrt2},\dfrac{1}{\sqrt2},0\right)^\top$, $u_3 = \left(0,-\dfrac{1}{\sqrt6},-\dfrac{1}{\sqrt6},\dfrac{2}{\sqrt6}\right)^\top$.

Solving $A^\top x = 0$ for a unit vector orthogonal to $u_1,u_2,u_3$ gives $u_4 = \dfrac12(1,-1,-1,-1)^\top$.

Result

Assembling the decomposition

Putting the three matrices together:

$A = \begin{pmatrix} \sqrt3/2 & 0 & 0 & 1/2 \\ \sqrt3/6 & -1/\sqrt2 & -1/\sqrt6 & -1/2 \\ \sqrt3/6 & 1/\sqrt2 & -1/\sqrt6 & -1/2 \\ \sqrt3/6 & 0 & 2/\sqrt6 & -1/2 \end{pmatrix} \begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 1/\sqrt3 & 1/\sqrt3 & 1/\sqrt3 \\ -1/\sqrt2 & 1/\sqrt2 & 0 \\ -1/\sqrt6 & -1/\sqrt6 & 2/\sqrt6 \end{pmatrix}$

Overview

SVD in one table

Object	What it is
Singular values	$\sigma_i = \sqrt{\lambda_i}$, with $\lambda_i$ eigenvalues of $A^\top A$; also $\sigma_i = \lVert Av_i\rVert$
$\Sigma$	$m\times n$ matrix $\begin{pmatrix} D & 0 \\ 0 & 0\end{pmatrix}$ with $\sigma_1 \ge \cdots \ge \sigma_r > 0$ on the diagonal of $D$
$V$ (right)	orthonormal eigenvectors of $A^\top A$ as columns; $A^\top A = V\Sigma^\top\Sigma V^\top$
$U$ (left)	orthonormal eigenvectors of $AA^\top$; for $i \le r$, $u_i = \frac{1}{\sigma_i}Av_i$, rest from $N(A^\top)$

Singular Value Decomposition

Why It Works: The Underlying Symmetric Matrices

Singular Values

The Three Matrices of the Decomposition

Procedure: Computing an SVD

Example: a 4×3 Matrix, Step by Step