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 the largest action of $A\in\mathbb{C}^{m\times n}$ , and then proceed by induction on the dimension of $A$ . We will denote hermitian conjugation by ${}^{T}$ . Norms for vectors in $\mathbb{C}^{n}$ will be the usual euclidean 2-norm $\left\|\cdot\right\|=\left\|\cdot\right\|_{2}$ and for matrix the induced by norm of vectors.

Let $\sigma_{1}=\left\|A\right\|$ . By a compactness argument, there must be vectors $v_{1}\in\mathbb{C}^{n},u^{*}_{1}\in\mathbb{C}^{m}$ with $\left\|v_{1}\right\|=1,\left\|u^{*}_{1}\right\|=\sigma_{1}$ and $u^{*}_{1}=Av_{1}$ . Normalize $u^{*}_{1}$ by setting $u_{1}=u^{*}_{1}/\left\|u^{*}_{1}\right\|$ and consider any extensions of $v_{1}$ to an orthonormal basis $\{v_{i}\}$ of $\mathbb{C}^{n}$ and of $u_{1}$ to an orthonormal basis $\{u_{j}\}$ of $\mathbb{C}^{m}$ ; let $U_{1}$ and $V_{1}$ denote the unitary matrices with columns $\{v_{i}\}$ and $\{u_{j}\}$ respectively. Then we have

U^{T}_{1}AV_{1}=S=\left(\begin{array}[]{cc}\sigma_{1}&w^{T}\\ 0&B\\ \end{array}\right)

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

\left\|\left(\begin{array}[]{cc}\sigma_{1}&w^{T}\\ 0&B\\ \end{array}\right)\left(\begin{array}[]{c}\sigma_{1}\\ w\end{array}\right)\right\|\geq\sigma_{1}^{2}+w^{2}=(\sigma_{1}^{2}+w^{2})^{1/% 2}\left\|\left(\begin{array}[]{c}\sigma_{1}\\ w\end{array}\right)\right\|

so that $\left\|S\right\|\geq(\sigma_{1}^{2}+w^{2})^{1/2}$ . But $U_{1}$ and $V_{1}$ are unitary matrix, hence $\left\|S\right\|=\sigma_{1}$ ; it therefore 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}$ . By the induction hypothesis $B$ has an SVD $B=U_{2}\Sigma_{2}V^{T}_{2}$ . Now it is easily verified that

A=U_{1}\left(\begin{array}[]{cc}1&0\\ 0&U_{2}\\ \end{array}\right)\left(\begin{array}[]{cc}\sigma_{1}&0\\ 0&\Sigma_{2}\\ \end{array}\right)\left(\begin{array}[]{cc}1&0\\ 0&V_{2}\\ \end{array}\right)^{T}V_{1}^{T}

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

For the uniqueness let $A=U\Sigma V^{T}$ a SVD for $A$ and let $e_{i}$ denote the i-th, $i=1\cdots min(m,n)$ vector of the canonical base of $\mathbb{C}^{n}$ . As $U$ and $V$ are unitary, $\left\|Ae_{i}\right\|=\sigma_{i}^{2}$ , so each $\sigma_{i}$ is uniquely determined.

∎

Title	proof of existence and uniqueness of singular value decomposition
Canonical name	ProofOfExistenceAndUniquenessOfSingularValueDecomposition
Date of creation	2013-03-22 17:07:46
Last modified on	2013-03-22 17:07:46
Owner	fernsanz (8869)
Last modified by	fernsanz (8869)
Numerical id	12
Author	fernsanz (8869)
Entry type	Proof
Classification	msc 65-00
Classification	msc 15-00