# 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 {\u2102}^{m\times n}$, and then proceed by induction^{} on the dimension^{}
of $A$. We will denote hermitian conjugation by ${}^{T}$. Norms for
vectors in ${\u2102}^{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 be
vectors ${v}_{1}\in {\u2102}^{n},{u}_{1}^{*}\in {\u2102}^{m}$ with $\parallel {v}_{1}\parallel =1,\parallel {u}_{1}^{*}\parallel ={\sigma}_{1}$ and ${u}_{1}^{*}=A{v}_{1}$. Normalize ${u}_{1}^{*}$ by
setting ${u}_{1}={u}_{1}^{*}/\parallel {u}_{1}^{*}\parallel $ and consider any extensions^{} of
${v}_{1}$ to an orthonormal basis $\{{v}_{i}\}$ of ${\u2102}^{n}$ and of ${u}_{1}$ to an
orthonormal basis $\{{u}_{j}\}$ of ${\u2102}^{m}$; let ${U}_{1}$ and ${V}_{1}$ denote
the unitary matrices^{} with columns $\{{v}_{i}\}$ and $\{{u}_{j}\}$
respectively. Then we have

$${U}_{1}^{T}A{V}_{1}=S=\left(\begin{array}{cc}\hfill {\sigma}_{1}\hfill & \hfill {w}^{T}\hfill \\ \hfill 0\hfill & \hfill B\hfill \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,

$$\parallel \left(\begin{array}{cc}\hfill {\sigma}_{1}\hfill & \hfill {w}^{T}\hfill \\ \hfill 0\hfill & \hfill B\hfill \end{array}\right)\left(\begin{array}{c}\hfill {\sigma}_{1}\hfill \\ \hfill w\hfill \end{array}\right)\parallel \ge {\sigma}_{1}^{2}+{w}^{2}={({\sigma}_{1}^{2}+{w}^{2})}^{1/2}\parallel \left(\begin{array}{c}\hfill {\sigma}_{1}\hfill \\ \hfill w\hfill \end{array}\right)\parallel $$ |

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}$; 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}{\mathrm{\Sigma}}_{2}{V}_{2}^{T}$. Now it
is easily verified that

$$A={U}_{1}\left(\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill {U}_{2}\hfill \end{array}\right)\left(\begin{array}{cc}\hfill {\sigma}_{1}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill {\mathrm{\Sigma}}_{2}\hfill \end{array}\right){\left(\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill {V}_{2}\hfill \end{array}\right)}^{T}{V}_{1}^{T}$$ |

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 ${\u2102}^{n}$. As $U$ and $V$ are unitary, $\parallel A{e}_{i}\parallel ={\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 |