# 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 ProofOfExistenceAndUniquenessOfSingularValueDecomposition 2013-03-22 17:07:46 2013-03-22 17:07:46 fernsanz (8869) fernsanz (8869) 12 fernsanz (8869) Proof msc 65-00 msc 15-00