Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/January 2009

Problem 3

Let $A\in R^{n\times m}$ with $n\ge m$. Assume $rank(A)=m$

Problem 3a

It is known that the symmetric matrix $A^{T}A$ can be factored as $A^{T}A=V\mathrm{\Lambda }{V}^T$ where the columns of $V$ are orthonormal eigenvectors of $A^{T}A$ and $\mathrm{\Lambda }$ is the diagonal matrix containing the corresponding eigenvalues. Using this as a starting point, derive the singular value decomposition of $A$. That is show that there is a real orthogonal matrix $U$ and a matrix $\mathrm{\Sigma }\in R^{n\times m}$ which is zero except for its diagonal entries ${\sigma }_1\ge {\sigma }_2\ge \dots \ge {\sigma }_m>0$ such that $A=U\mathrm{\Sigma }{V}^T$

Solution 3a

We want to show

$A=U\mathrm{\Sigma }{V}^T$

which is equivalent to

$AV=U\mathrm{\Sigma }$

Decompose Lambda

Decompose $\mathrm{\Lambda }$ into ${\mathrm{\Sigma }}^T\mathrm{\Sigma }$ i.e.

$\underset{\mathrm{\Lambda }\in R^{m\times m}}{\underbrace{\left[\begin{array}{cccc}{\sigma }_1& & & \\ & {\sigma }_2& & \\ & & \ddots & \\ & & & {\sigma }_m\end{array}\right]}}=\underset{{\mathrm{\Sigma }}^T\in R^{m\times n}}{\underbrace{\left[\begin{array}{ccccccc}\sqrt{{\sigma }_1}& & & & 0& \cdots & 0\\ & \sqrt{{\sigma }_2}& & & 0& & \\ & & \ddots & & ⋮& & \\ & & & \sqrt{{\sigma }_m}& 0& \cdots & 0\end{array}\right]}}\underset{\mathrm{\Sigma }\in R^{n\times m}}{\underbrace{\left[\begin{array}{cccc}\sqrt{{\sigma }_1}& & & \\ & \sqrt{{\sigma }_2}& & \\ & & \ddots & \\ & & & \sqrt{{\sigma }_m}\\ 0& \cdots & & 0\\ ⋮& ⋮& & ⋮\\ 0& \cdots & 0& 0\end{array}\right]}}$

We can assume ${\sigma }_1\ge {\sigma }_2\ge \dots \ge {\sigma }_n>0$ since otherwise we could just rearrange the columns of $V$.

Define U

Let $U=AV{\mathrm{\Sigma }}^{-1}$ where

${\mathrm{\Sigma }}^{-1}=\left(\begin{array}{ccccccc}\frac{1}{\sqrt{{\sigma }_1}}& & & & 0& \cdots & 0\\ & \frac{1}{\sqrt{{\sigma }_2}}& & & 0& & \\ & & \ddots & & ⋮& & \\ & & & \frac{1}{\sqrt{{\sigma }_m}}& 0& \cdots & 0\end{array}\right),$

Verify U orthogonal

$\begin{array}{cc}U{U}^T& =AV{\mathrm{\Sigma }}^{-1}{\mathrm{\Sigma }}^{-T}{V}^T{A}^T\\ & =AV{\mathrm{\Lambda }}^{-1}{V}^T{A}^T\\ & =A{A}^{-1}{A}^{-T}{A}^T\\ & =I\\ \\ U^{T}U& ={\mathrm{\Sigma }}^{-T}{V}^T{A}^{T}AV{\mathrm{\Sigma }}^{-1}\\ & ={\mathrm{\Sigma }}^{-T}{V}^{T}V\mathrm{\Lambda }{V}^{T}V{\mathrm{\Sigma }}^{-1}\\ & =I\end{array}$