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

Problem 3

Let $A\in R^{n\times m}\!\,$ with $n\geq 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\Lambda V^{T}\!\,$ where the columns of $V\!\,$ are orthonormal eigenvectors of $A^{T}A\!\,$ and $\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 $\Sigma \in R^{n\times m}\!\,$ which is zero except for its diagonal entries $\sigma _{1}\geq \sigma _{2}\geq \ldots \geq \sigma _{m}>0\!\,$ such that $A=U\Sigma V^{T}\!\,$

Solution 3a

We want to show

$A=U\Sigma V^{T}\!\,$

which is equivalent to

$AV=U\Sigma \!\,$

Decompose Lambda

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

$\underbrace {\begin{bmatrix}\sigma _{1}&&&\\&\sigma _{2}&&\\&&\ddots &\\&&&\sigma _{m}\end{bmatrix}} _{\Lambda \in R^{m\times m}}=\underbrace {\begin{bmatrix}{\sqrt {\sigma _{1}}}&&&&0&\cdots &0\\&{\sqrt {\sigma _{2}}}&&&0&&\\&&\ddots &&\vdots &&\\&&&{\sqrt {\sigma _{m}}}&0&\cdots &0\end{bmatrix}} _{\Sigma ^{T}\in R^{m\times n}}\underbrace {\begin{bmatrix}{\sqrt {\sigma _{1}}}&&&\\&{\sqrt {\sigma _{2}}}&&\\&&\ddots &\\&&&{\sqrt {\sigma _{m}}}\\0&\cdots &&0\\\vdots &\vdots &&\vdots \\0&\cdots &0&0\end{bmatrix}} _{\Sigma \in R^{n\times m}}\!\,$

We can assume $\sigma _{1}\geq \sigma _{2}\geq \ldots \geq \sigma _{n}>0\!\,$ since otherwise we could just rearrange the columns of $V\!\,$.

Define U

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

$\Sigma ^{-1}=\left({\begin{array}{ccccccc}{\frac {1}{\sqrt {\sigma _{1}}}}&&&&0&\cdots &0\\&{\frac {1}{\sqrt {\sigma _{2}}}}&&&0&&\\&&\ddots &&\vdots &&\\&&&{\frac {1}{\sqrt {\sigma _{m}}}}&0&\cdots &0\end{array}}\right),$

Verify U orthogonal

${\begin{aligned}UU^{T}&=AV\Sigma ^{-1}\Sigma ^{-T}V^{T}A^{T}\\&=AV\Lambda ^{-1}V^{T}A^{T}\\&=AA^{-1}A^{-T}A^{T}\\&=I\\\\U^{T}U&=\Sigma ^{-T}V^{T}A^{T}AV\Sigma ^{-1}\\&=\Sigma ^{-T}V^{T}V\Lambda V^{T}V\Sigma ^{-1}\\&=I\end{aligned}}\!\,$