proof of existence and uniqueness of singular value decomposition

Proof of existence and uniqueness of SVDFernando Sanz Gamiz

Proof.

To prove existence of the SVD, we isolate the direction of thelargest action of $A\in {ℂ}^{m\times n}$, and then proceed by induction on the dimensionof $A$. We will denote hermitian conjugation by ${}^T$. Norms forvectors in ${ℂ}^n$ will be the usual euclidean 2-norm $\parallel \cdot \parallel =\parallel \cdot {\parallel }_2$ and for matrix the induced by norm of vectors.

Let ${\sigma }_1=\parallel A\parallel$. By a compactness argument, there must bevectors $v_1\in {ℂ}^n,u_1^{*}\in {ℂ}^m$ with $\parallel v_1\parallel =1,\parallel u_1^{*}\parallel ={\sigma }_1$ and $u_1^{*}=A{v}_1$. Normalize $u_1^{*}$ bysetting $u_1=u_1^{*}/\parallel u_1^{*}\parallel$ and consider any extensions of$v_1$ to an orthonormal basis $\{v_i\}$ of ${ℂ}^n$ and of $u_1$ to anorthonormal basis $\{u_j\}$ of ${ℂ}^m$; let $U_1$ and $V_1$ denotethe unitary matrices with columns $\{v_i\}$ and $\{u_j\}$respectively. Then we have

where $0$ is a column vector of dimension $m-1$, $w^T$ isa row vector of dimension $n-1$, and $B$ is a matrix of dimension$(m-1)\times (n-1)$. Now,

so that $\parallel S\parallel \ge {({\sigma }_1^2+w^2)}^{1/2}$. But $U_1$and $V_1$ are unitary matrix, hence $\parallel S\parallel ={\sigma }_1$; ittherefore implies $w=0$.

If $n=1$ or $m=1$ we are done. Otherwise the submatrix $B$describes the action of $A$ on the subspace orthogonal to $v_1$. Bythe induction hypothesis $B$ has an SVD $B=U_2{\mathrm{\Sigma }}_2{V}_2^T$. Now itis easily verified that

is an SVD of $A$. completing the proof of existence.

For the uniqueness let $A=U\mathrm{\Sigma }{V}^T$ a SVD for $A$ and let $e_i$denote the i-th, $i=1\mathrm{\cdots }min(m,n)$ vector of the canonical base of ${ℂ}^n$. As $U$ and$V$ are unitary, $\parallel A{e}_i\parallel ={\sigma }_i^2$, so each${\sigma }_i$ is uniquely determined.

∎