Singular Value Decomposition

Thin SVD

Let $A \in M_{m,n}$ with $m \le n$. There are a unitary $U \in M_m$, a diagonal $\Sigma = \mathrm{diag}(\sigma_1, \ldots, \sigma_m) \in M_m$ with $\sigma_1 \ge \cdots \ge \sigma_m \ge 0$, and $W \in M_{m,n}$ with orthonormal rows such that

$$A = U \Sigma W$$

Proof

1. $AA^*$ is Hermitian PSD, so $AA^* = UDU^*$ with $D = \mathrm{diag}(\sigma_1^2, \ldots, \sigma_m^2)$, $\sigma_i \ge 0$ decreasing. Let $k$ be the last index with $\sigma_k > 0$, and $\mu_i$ the columns of $U$.
2. Define the $i$th row of $W$ as $\frac{1}{\sigma_i} \mu_i^* A$ for $i = 1, \ldots, k$. These are orthonormal, since $\frac{1}{\sigma_i \sigma_j} \mu_i^* AA^* \mu_j = \frac{\sigma_j^2}{\sigma_i \sigma_j} \mu_i^* \mu_j$.
3. For $i = k+1, \ldots, m$ define the rows in any way so they are orthonormal to the others, by Gram-Schmidt.
4. For $i = k+1, \ldots, m$, $AA^*\mu_i = 0 \Rightarrow \mu_i^*AA^*\mu_i = 0 \Rightarrow \|A^*\mu_i\|_2^2 = 0 \Rightarrow \mu_i^*A = \vec{0}^T$. So $U^*A = \Sigma W$.

SVD

For $A \in M_{m,n}$ there are unitary $U \in M_m$ and $V \in M_n$, and a diagonal $\Sigma \in M_{m,n}$ with $\sigma_1 = \Sigma_{11} \ge \sigma_2 = \Sigma_{22} \ge \cdots \ge 0$, such that

$$A = U \Sigma V^*$$

Proof If $m \le n$, complete the rows of $W$ to a unitary matrix by Gram-Schmidt,

$$A = U \Sigma W = U \begin{bmatrix} \Sigma & 0 \end{bmatrix} \begin{bmatrix} W \\ \text{Gram-Schmidt} \end{bmatrix}$$

If $m > n$, take the SVD $A^* = U\Sigma V^*$, then $A = V\Sigma^*U^*$ is an SVD.

Consequences

Let $A = U\Sigma V^*$ with columns $\mu_i$ of $U$ and $v_i$ of $V$, and $k$ such that $\sigma_k > 0$, $\sigma_{k+1} = 0$. Then

1. $A = \sum_{i=1}^{k} \sigma_i \mu_i v_i^*$,
2. $\mathrm{rank}\, A = k$, $\mathrm{range}\, A = \mathrm{span}\{\mu_1, \ldots, \mu_k\}$, $\mathrm{null}(A) = \mathrm{span}\{v_{k+1}, \ldots, v_n\}$,
3. $\mathrm{rank}\, A^* = k$, $\mathrm{range}\, A^* = \mathrm{span}\{v_1, \ldots, v_k\}$, $\mathrm{null}(A^*) = \mathrm{span}\{\mu_{k+1}, \ldots, \mu_m\}$,
4. $\|A\|_F = \|\Sigma\|_F = \sqrt{\sum \sigma_i^2}$ and $\|A\|_2 = \max_{x \neq 0} \frac{\|Ax\|_2}{\|x\|_2} = \sigma_1$.

Polar Decomposition

For $A \in M_n$, $A = PW$ with $P$ PSD and $W$ unitary.

$(\Rightarrow)$ From the SVD,

$$A = U\Sigma V^* = \underbrace{U\Sigma U^*}_{P} \, \underbrace{UV^*}_{W}$$

$(\Leftarrow)$ Conversely, a polar decomposition gives an SVD. Let $P = U\Sigma U^*$ and $V := W^*U$. Then $A = PW = U\Sigma U^*W = U\Sigma V^*$.