Singular Value Decomposition

The matrix $\mathbf{A}^H \mathbf{A} \in \mathbb{C}^{n \times n}$ is Hermitian and positive semidefinite (for any $\mathbf{x}$, $\mathbf{x}^H (\mathbf{A}^H \mathbf{A}) \mathbf{x} = \|\mathbf{A}\mathbf{x}\|^2 \geq 0$). By the spectral theorem (TSpectral Theorem for Hermitian Matrices), there exists a unitary matrix $\mathbf{V} = [\mathbf{v}_1 \mid \cdots \mid \mathbf{v}_n] \in \mathbb{C}^{n \times n}$ and a real diagonal matrix $\mathbf{D} = \operatorname{diag}(\lambda_1, \ldots, \lambda_n)$ with $\lambda_1 \geq \cdots \geq \lambda_n \geq 0$ such that $$\mathbf{A}^H \mathbf{A} = \mathbf{V} \mathbf{D} \mathbf{V}^H.$$ Let $r = \operatorname{rank}(\mathbf{A})$. Then exactly $r$ eigenvalues are strictly positive: $\lambda_1 \geq \cdots \geq \lambda_r > 0$ and $\lambda_{r+1} = \cdots = \lambda_n = 0$.

Why $\operatorname{rank}(\mathbf{A}^H\mathbf{A}) = \operatorname{rank}(\mathbf{A})$: Note that $\mathcal{N}(\mathbf{A}^H \mathbf{A}) = \mathcal{N}(\mathbf{A})$, since $\mathbf{A}^H \mathbf{A} \mathbf{x} = \mathbf{0}$ implies $\|\mathbf{A}\mathbf{x}\|^2 = \mathbf{x}^H \mathbf{A}^H \mathbf{A} \mathbf{x} = 0$, hence $\mathbf{A}\mathbf{x} = \mathbf{0}$. The converse is trivial. By the rank--nullity theorem, $\operatorname{rank}(\mathbf{A}^H\mathbf{A}) = \operatorname{rank}(\mathbf{A}) = r$.

Define the singular values $$\sigma_i = \sqrt{\lambda_i} > 0, \qquad i = 1, \ldots, r.$$

For each $i = 1, \ldots, r$, define $$\mathbf{u}_i = \frac{1}{\sigma_i} \mathbf{A} \mathbf{v}_i \in \mathbb{C}^m.$$

Claim: The set $\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$ is orthonormal.

Proof of claim: For $1 \leq i, k \leq r$, $$\mathbf{u}_i^H \mathbf{u}_k = \frac{1}{\sigma_i \sigma_k} (\mathbf{A}\mathbf{v}_i)^H (\mathbf{A}\mathbf{v}_k) = \frac{1}{\sigma_i \sigma_k} \mathbf{v}_i^H (\mathbf{A}^H \mathbf{A}) \mathbf{v}_k = \frac{1}{\sigma_i \sigma_k} \mathbf{v}_i^H (\sigma_k^2 \mathbf{v}_k) = \frac{\sigma_k}{\sigma_i} \mathbf{v}_i^H \mathbf{v}_k = \frac{\sigma_k}{\sigma_i} \delta_{ik} = \delta_{ik},$$ where we used $\mathbf{A}^H \mathbf{A} \mathbf{v}_k = \lambda_k \mathbf{v}_k = \sigma_k^2 \mathbf{v}_k$ and the orthonormality of $\{\mathbf{v}_i\}$.

The vectors $\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$ form an orthonormal set in $\mathbb{C}^m$. Since $r \leq m$, we can extend this set to an orthonormal basis $\{\mathbf{u}_1, \ldots, \mathbf{u}_r, \mathbf{u}_{r+1}, \ldots, \mathbf{u}_m\}$ of $\mathbb{C}^m$ (for instance by Gram--Schmidt applied to any completion).

Claim: $\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$ spans $\mathcal{R}(\mathbf{A})$.

Proof: Every $\mathbf{y} \in \mathcal{R}(\mathbf{A})$ has the form $\mathbf{y} = \mathbf{A}\mathbf{x}$ for some $\mathbf{x} \in \mathbb{C}^n$. Expand $\mathbf{x} = \sum_{i=1}^n c_i \mathbf{v}_i$ (since the $\mathbf{v}_i$ form a basis). Then $\mathbf{y} = \sum_{i=1}^n c_i \mathbf{A}\mathbf{v}_i = \sum_{i=1}^r c_i \sigma_i \mathbf{u}_i$, where we used $\mathbf{A}\mathbf{v}_i = \sigma_i \mathbf{u}_i$ for $i \leq r$ and $\mathbf{A}\mathbf{v}_i = \mathbf{0}$ for $i > r$ (since $\mathbf{v}_i \in \mathcal{N}(\mathbf{A})$ for $i > r$). Therefore $\mathbf{y} \in \operatorname{span}\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$.

Conversely, each $\mathbf{u}_i = \frac{1}{\sigma_i}\mathbf{A}\mathbf{v}_i \in \mathcal{R}(\mathbf{A})$. Hence $\operatorname{span}\{\mathbf{u}_1, \ldots, \mathbf{u}_r\} = \mathcal{R}(\mathbf{A})$.

Define the unitary matrix $$\mathbf{U} = [\mathbf{u}_1 \mid \cdots \mid \mathbf{u}_m] \in \mathbb{C}^{m \times m}.$$

Define the $m \times n$ matrix $\mathbf{\Sigma}$ with $(\mathbf{\Sigma})_{ii} = \sigma_i$ for $i = 1, \ldots, \min(m,n)$ and all other entries zero, where $\sigma_i = 0$ for $i > r$.

We must verify $\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^H$. Since $\mathbf{V}$ is unitary, it suffices to show $\mathbf{A}\mathbf{V} = \mathbf{U}\mathbf{\Sigma}$, i.e., to verify $\mathbf{A}\mathbf{v}_i = \sigma_i \mathbf{u}_i$ for every $i$.

Case $1 \leq i \leq r$: By construction, $\mathbf{u}_i = \frac{1}{\sigma_i}\mathbf{A}\mathbf{v}_i$, so $\mathbf{A}\mathbf{v}_i = \sigma_i \mathbf{u}_i$. $\checkmark$

Case $r < i \leq n$: Since $\mathbf{v}_i \in \mathcal{N}(\mathbf{A}^H\mathbf{A}) = \mathcal{N}(\mathbf{A})$, we have $\mathbf{A}\mathbf{v}_i = \mathbf{0}$. Also $\sigma_i = 0$, so $\sigma_i \mathbf{u}_i = \mathbf{0}$. Hence $\mathbf{A}\mathbf{v}_i = \mathbf{0} = \sigma_i \mathbf{u}_i$. $\checkmark$

Therefore $\mathbf{A}\mathbf{V} = \mathbf{U}\mathbf{\Sigma}$, which gives $$\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^H.$$

Outer-product form. Equivalently, $$\mathbf{A} = \sum_{i=1}^{r} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^H,$$ which expresses $\mathbf{A}$ as a sum of $r$ rank-one matrices, each weighted by the corresponding singular value. $\blacksquare$

The singular values $\sigma_1 \geq \cdots \geq \sigma_r > 0$ are uniquely determined by $\mathbf{A}$, because they are the positive square roots of the eigenvalues of $\mathbf{A}^H \mathbf{A}$, which are uniquely determined.

The singular vectors, however, are generally not unique:

1. Phase ambiguity. If $(\mathbf{u}_i, \mathbf{v}_i)$ is a singular vector pair, then so is $(e^{j\theta}\mathbf{u}_i, e^{j\theta}\mathbf{v}_i)$ for any $\theta \in \mathbb{R}$, since $\mathbf{A}(e^{j\theta}\mathbf{v}_i) = e^{j\theta}\sigma_i \mathbf{u}_i = \sigma_i (e^{j\theta}\mathbf{u}_i)$.

2. Repeated singular values. If $\sigma_i = \sigma_{i+1} = \cdots = \sigma_{i+p-1}$, then any orthonormal basis of the corresponding right (resp. left) singular subspace yields a valid SVD. This is analogous to eigenspaces of repeated eigenvalues in the spectral theorem.

Since $\mathbf{A} = \sum_{i=1}^{r} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^H$ and $\mathbf{A}_k = \sum_{i=1}^{k} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^H$, we have $$\mathbf{A} - \mathbf{A}_k = \sum_{i=k+1}^{r} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^H.$$ The Frobenius norm satisfies $\|\mathbf{M}\|_F^2 = \operatorname{tr}(\mathbf{M}^H \mathbf{M})$. Computing: $$\|\mathbf{A} - \mathbf{A}_k\|_F^2 = \operatorname{tr}\!\left(\sum_{i=k+1}^{r} \sum_{l=k+1}^{r} \sigma_i \sigma_l \, \mathbf{v}_i \mathbf{u}_i^H \mathbf{u}_l \mathbf{v}_l^H\right) = \sum_{i=k+1}^{r} \sigma_i^2,$$ where we used $\mathbf{u}_i^H \mathbf{u}_l = \delta_{il}$ and $\operatorname{tr}(\mathbf{v}_i \mathbf{v}_i^H) = \mathbf{v}_i^H \mathbf{v}_i = 1$.

Recall that the Frobenius norm is unitarily invariant: $\|\mathbf{M}\|_F = \|\mathbf{P}\mathbf{M}\mathbf{Q}\|_F$ for any unitary $\mathbf{P}$ and $\mathbf{Q}$. This is because $\|\mathbf{P}\mathbf{M}\mathbf{Q}\|_F^2 = \operatorname{tr}(\mathbf{Q}^H \mathbf{M}^H \mathbf{P}^H \mathbf{P} \mathbf{M} \mathbf{Q}) = \operatorname{tr}(\mathbf{Q}^H \mathbf{M}^H \mathbf{M} \mathbf{Q}) = \operatorname{tr}(\mathbf{M}^H \mathbf{M} \mathbf{Q} \mathbf{Q}^H) = \operatorname{tr}(\mathbf{M}^H \mathbf{M}) = \|\mathbf{M}\|_F^2$.

Consequently, for any $\mathbf{B} \in \mathbb{C}^{m \times n}$, $$\|\mathbf{A} - \mathbf{B}\|_F = \|\mathbf{U}^H(\mathbf{A} - \mathbf{B})\mathbf{V}\|_F = \|\mathbf{\Sigma} - \tilde{\mathbf{B}}\|_F,$$ where $\tilde{\mathbf{B}} = \mathbf{U}^H \mathbf{B} \mathbf{V}$ has $\operatorname{rank}(\tilde{\mathbf{B}}) = \operatorname{rank}(\mathbf{B}) \leq k$.

The problem thus reduces to: among all $m \times n$ matrices $\tilde{\mathbf{B}}$ of rank at most $k$, which one minimizes $\|\mathbf{\Sigma} - \tilde{\mathbf{B}}\|_F$?

Let $\mathbf{B}$ be any matrix with $\operatorname{rank}(\mathbf{B}) \leq k$. Then $\dim \mathcal{N}(\mathbf{B}) \geq n - k$.

Consider the $(k+1)$-dimensional subspace $\mathcal{V}_{k+1} = \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_{k+1}\}$. By a dimension argument: $$\dim(\mathcal{N}(\mathbf{B}) \cap \mathcal{V}_{k+1}) \geq \dim \mathcal{N}(\mathbf{B}) + \dim \mathcal{V}_{k+1} - n \geq (n - k) + (k + 1) - n = 1.$$ So there exists a unit vector $\mathbf{z} \in \mathcal{N}(\mathbf{B}) \cap \mathcal{V}_{k+1}$. Write $\mathbf{z} = \sum_{i=1}^{k+1} \alpha_i \mathbf{v}_i$ with $\sum_{i=1}^{k+1} |\alpha_i|^2 = 1$.

Since $\mathbf{B}\mathbf{z} = \mathbf{0}$: $$\|\mathbf{A} - \mathbf{B}\|_F^2 \geq \|(\mathbf{A} - \mathbf{B})\mathbf{z}\|^2 = \|\mathbf{A}\mathbf{z}\|^2 = \left\|\sum_{i=1}^{k+1} \alpha_i \sigma_i \mathbf{u}_i\right\|^2 = \sum_{i=1}^{k+1} |\alpha_i|^2 \sigma_i^2 \geq \sigma_{k+1}^2 \sum_{i=1}^{k+1} |\alpha_i|^2 = \sigma_{k+1}^2.$$

This establishes $\|\mathbf{A} - \mathbf{B}\|_F^2 \geq \sigma_{k+1}^2$. For the Frobenius norm result, we need a tighter bound. Since the inequality $\|\mathbf{A} - \mathbf{B}\|_F^2 \geq \|(\mathbf{A} - \mathbf{B})\mathbf{z}\|^2$ holds for a single vector, we apply the argument to $n - k$ orthogonal vectors in $\mathcal{N}(\mathbf{B})$.

Let $\{\mathbf{z}_1, \ldots, \mathbf{z}_{n-k}\}$ be an orthonormal basis of $\mathcal{N}(\mathbf{B})$ and form $\mathbf{Z} = [\mathbf{z}_1 \mid \cdots \mid \mathbf{z}_{n-k}]$. Then $$\|\mathbf{A} - \mathbf{B}\|_F^2 \geq \|(\mathbf{A} - \mathbf{B})\mathbf{Z}\|_F^2 = \|\mathbf{A}\mathbf{Z}\|_F^2 = \operatorname{tr}(\mathbf{Z}^H \mathbf{A}^H \mathbf{A} \mathbf{Z}).$$ By the Cauchy interlacing inequalities (a consequence of Courant--Fischer), the eigenvalues of the $(n-k) \times (n-k)$ matrix $\mathbf{Z}^H \mathbf{A}^H \mathbf{A} \mathbf{Z}$ satisfy $\mu_i \geq \lambda_{k+i}(\mathbf{A}^H\mathbf{A}) = \sigma_{k+i}^2$ for each $i = 1, \ldots, n-k$. Therefore $$\operatorname{tr}(\mathbf{Z}^H \mathbf{A}^H \mathbf{A} \mathbf{Z}) = \sum_{i=1}^{n-k} \mu_i \geq \sum_{i=1}^{n-k} \sigma_{k+i}^2 = \sum_{i=k+1}^{r} \sigma_i^2.$$

From Step 1, $\|\mathbf{A} - \mathbf{A}_k\|_F^2 = \sum_{i=k+1}^{r} \sigma_i^2$. From Step 3, for any rank-$\leq k$ matrix $\mathbf{B}$, $\|\mathbf{A} - \mathbf{B}\|_F^2 \geq \sum_{i=k+1}^{r} \sigma_i^2$.

Since $\mathbf{A}_k$ has rank at most $k$ (it is a sum of $k$ rank-one matrices) and achieves the lower bound, it is a minimizer: $$\mathbf{A}_k = \arg\min_{\operatorname{rank}(\mathbf{B}) \leq k} \|\mathbf{A} - \mathbf{B}\|_F.$$

Spectral norm case. The spectral (operator) norm $\|\mathbf{M}\|_2 = \sigma_1(\mathbf{M})$ is also unitarily invariant. The subspace intersection argument from Step 3 (applied with a single vector $\mathbf{z}$) gives $\|\mathbf{A} - \mathbf{B}\|_2 \geq \sigma_{k+1}$. Since $\|\mathbf{A} - \mathbf{A}_k\|_2 = \sigma_{k+1}$ (the largest singular value of $\sum_{i=k+1}^r \sigma_i \mathbf{u}_i \mathbf{v}_i^H$ is $\sigma_{k+1}$), the bound is tight. $\blacksquare$