Solve the problems for your appropriate course track. Problems probe understanding of the definitions and results from the module on floating point arithmetic and linear algebra. Formulate your answers clearly, cogently, and include a concise description of your approach. Each question is meant to be completely answered within ten minutes. Allowed test time is 75 minutes.

1Common problems

1. Matrix $𝑨\in {ℝ}^{m\times m}$, $\mathrm{rank}\left(𝑨\right)=m$, has the singular value decomposition (SVD) $𝑨=𝑼𝚺{𝑽}^T$ ($𝑼{𝑼}^T={𝑼}^T𝑼=𝑰$, $𝑽{𝑽}^T={𝑽}^T𝑽=𝑰$, $𝚺=\mathrm{diag}({\sigma }_1,..,{\sigma }_m)$, ${\sigma }_1⩾{\sigma }_2⩾\cdots ⩾{\sigma }_m>0$) and the pseudoinverse ${𝑨}^{+}=𝑽{𝚺}^{+}{𝑼}^T$, ${𝚺}^{+}=\mathrm{diag}(1/{\sigma }_1,..,1/{\sigma }_m)$. Find the SVDs of:

   1. ${𝑨}^T𝑨$ ;

   2. ${({𝑨}^T𝑨)}^{+}$ ;

   3. ${({𝑨}^T𝑨)}^{+}{𝑨}^T$ ;

   4. $𝑨{({𝑨}^T𝑨)}^{+}$ ;

   5. $𝑨{({𝑨}^T𝑨)}^{+}{𝑨}^T$ .

   Solution.

   1. ${𝑨}^T𝑨={(𝑼𝚺{𝑽}^T)}^T𝑼𝚺{𝑽}^T=𝑽{𝚺}^T{𝑼}^T𝑼𝚺{𝑽}^T=𝑽{𝚺}^T𝚺{𝑽}^T=𝑽{𝚺}^2{𝑽}^T$, since ${𝚺}^T=𝚺$. The SVD is

      ${\displaystyle {𝑨}^T𝑨=𝑽{𝚺}^2{𝑽}^T}$

      and the singular values of ${𝑨}^T𝑨$ are the squares of those of $𝑨$.

   2. ${({𝑨}^T𝑨)}^{+}={(𝑽{𝚺}^2{𝑽}^T)}^{+}=𝑽{\left({𝚺}^2\right)}^{+}{𝑽}^T$. This is not an SVD since

      ${\displaystyle {\left({𝚺}^2\right)}^{+}=\mathrm{diag}(1/{\sigma }_1^2,..,1/{\sigma }_m^2),1/{\sigma }_1^2⩽1/{\sigma }_2^2⩽\cdots ⩽1/{\sigma }_m^2.}$

      Introduce permutation matrix $𝑷=\left[\begin{array}{llll}{𝒆}_m& {𝒆}_{m-1}& ...& {𝒆}_1\end{array}\right]$ which is orthogonal, $𝑷{𝑷}^T=𝑰$ and symmetric $𝑷={𝑷}^T$ to obtain

      ${\displaystyle {\left({𝚺}^2\right)}^{+}𝑷=\mathrm{diag}(1/{\sigma }_m^2,..,1/{\sigma }_1^2)=𝚲,}$

      the correct ordering and the SVD

      ${\displaystyle {({𝑨}^T𝑨)}^{+}=𝑽{\left({𝚺}^2\right)}^{+}{𝑽}^T=𝑽{\left({𝚺}^2\right)}^{+}𝑷{𝑷}^T{𝑽}^T=𝑽𝚲{(𝑽𝑷)}^T,}$

      since $𝑽𝑷$, the product of two orthogonal matrices, is itself orthogonal.

   3. Calculate

      ${\displaystyle {({𝑨}^T𝑨)}^{+}{𝑨}^T=𝑽𝚲{(𝑽𝑷)}^T𝑽{𝚺}^T{𝑼}^T=𝑽𝚲{𝑷}^T{𝑽}^T𝑽𝚺{𝑼}^T=𝑽𝚲{𝑷}^T𝚺{𝑼}^T.}$

      Since

      ${\displaystyle {𝑷}^T𝚺=𝑷𝚺=\mathrm{diag}({\sigma }_m,..,{\sigma }_1),}$

      obtain

      ${\displaystyle 𝚲{𝑷}^T𝚺=\mathrm{diag}(1/{\sigma }_m,..,1/{\sigma }_1)=𝚪,}$

      and the SVD

      ${\displaystyle {({𝑨}^T𝑨)}^{+}{𝑨}^T=𝑽𝚪{𝑼}^T.}$

   4. Calculate

      ${\displaystyle 𝑨{({𝑨}^T𝑨)}^{+}=𝑼𝚺{𝑽}^T𝑽𝚲{(𝑽𝑷)}^T=𝑼𝚺𝚲{(𝑽𝑷)}^T=𝑼𝚪{(𝑽𝑷)}^T,}$

      which is an SVD.

   5. Use above and $𝚺𝚪=𝑰$ to write

      ${\displaystyle 𝑨{({𝑨}^T𝑨)}^{+}{𝑨}^T=𝑼𝚺{𝑽}^T𝑽𝚪{𝑼}^T=𝑼𝚺𝚪{𝑼}^T=𝑰.}$

2Track 1

1. Write pseudo-code to accurately evaluate the sum

   ${\displaystyle S_{2n}=\sum _{k=1}^{2n}\frac{{(-1)}^{k+1}}{k}{x}^k}$

   in floating point arithmetic when $x=1+\epsilon$, $1\gg \epsilon >0$. (${lim}_{n\to \infty }{S}_{2n}=\ln (1+x)$).

   Solution. There is possible loss of precision from successive terms of alternating signs, the effect of which can be attenuated by adding two terms at a time to the sum accumulator

   ${\displaystyle S_{2n}=\sum _{k=1}^n{x}^{2k-1}(\frac{1}{2k-1}-\frac{x}{2k})}$

   $S=0$; $y=x$; $x2=x^2$

   for $k$=1 to $n$

   $l=2k;d=1/(l-1)-x/l$

   $t=y\cdot l$; $S=S+t$; $y=y\cdot x2$

2. Use the SVD of $𝑨\in {ℝ}^{m\times n}$ to express the Moore-Penrose pseudoinverse as a sum of rank-one matrices.

   Solution. The SVD of $𝑨$ is $𝑨=𝑼𝚺{𝑽}^T$ and the pseudoinverse is written as

   ${\displaystyle {𝑨}^{+}=𝑽{𝚺}^{+}{𝑼}^T=\left[\begin{array}{lll}{𝒗}_1& ..& {𝒗}_n\end{array}\right]\left[\begin{array}{lllll}1/{\sigma }_1& & & & \\ & \ddots & & & \\ & & 1/{\sigma }_r& & \\ & & & 0& \end{array}\right]\left[\begin{array}{l}{𝒖}_1^T\\ ⋮\\ {𝒖}_m^T\end{array}\right]=\sum _{j=1}^r\frac{1}{{\sigma }_j}{𝒗}_j{𝒖}_j^T,}$

   a sum of the rank-1 updates ${𝒗}_j{𝒖}_j^T/{\sigma }_j$.

3Track 2

1. Let $𝑨\in {ℝ}^{m\times n}$. Show that the Moore-Penrose pseudoinverse $𝑿={𝑨}^{+}$ minimizes ${||𝑨𝑿-𝑰||}_F$ over all $n$ by $m$ matrices.

   Solution. The squared Frobenius norm of $𝑨𝑿-𝑰=\left[\begin{array}{lll}𝑨{𝒙}_1-{𝒆}_1& & 𝑨{𝒙}_n-{𝒆}_n\end{array}\right]$ is the sum of its squared column vector 2-norms

   ${\displaystyle {||𝑨𝑿-𝑰||}_F^2=\sum _{j=1}^n{||𝑨{𝒙}_j-{𝒆}_j||}_2^2,}$

   and the minimum is attained by the solution of the $n$ least squares problems

   ${\displaystyle {min}_{{𝒙}_j}{||𝑨{𝒙}_j-{𝒆}_j||}_2\Rightarrow {𝒙}_j=𝑽{𝚺}^{+}{𝑼}^T{𝒆}_j\Rightarrow 𝑿={𝑨}^{+}𝑰={𝑨}^{+}.}$

2. Let $𝑨\in {ℂ}^{m\times m}$ be skew-Hermitian, i.e., ${𝑨}^{\ast }=-𝑨$. Prove that:

   1. $𝑰-𝑨$ is nonsingular;

   2. $𝑪={(𝑰-𝑨)}^{-1}(𝑰+𝑨)$ is unitary.

   Solution. a) For $m=1$, $a+a^{\ast }=0$, and $b=1-a$ nonsingular implies ${||b||}_2^2=b^{\ast }b>0$, readily verified

   ${\displaystyle b^{\ast }b=(1-a^{\ast })(1-a)=1+a^{\ast }a>0.}$

   This also holds for $m>1$, $𝑨+{𝑨}^{\ast }=0$, and $𝑩=𝑰-𝑨$ nonsingular implies ${||𝑩𝒙||}_2^2={||𝒚||}_2^2>0$ for any $𝒙$ of unit norm. Compute

   ${\displaystyle {𝒚}^{\ast }𝒚={𝒙}^{\ast }{𝑩}^{\ast }𝑩𝒙={𝒙}^{\ast }(𝑰+{𝑨}^{\ast }𝑨)𝒙=1+{||𝒚||}_2^2>0.}$

   b) Again, use $m=1$ to gain insight in which case $c={(1-a)}^{-1}(1+a)$ and compute

   ${\displaystyle c^{\ast }c=(1+a^{\ast }){(1-a^{\ast })}^{-1}{(1-a)}^{-1}(1+a)=(1-a){\left[(1-a)(1+a)\right]}^{-1}(1+a)=(1-a){(1-a^2)}^{-1}(1+a)}$ ${\displaystyle c^{\ast }c=(1-a){\left[(1+a)(1-a)\right]}^{-1}(1+a)=(1-a){(1-a)}^{-1}{(1+a)}^{-1}(1+a)=1}$

   Similarily, for $m>1$

   ${\displaystyle {𝑪}^{\ast }𝑪=(𝑰+{𝑨}^{\ast }){(𝑰-{𝑨}^{\ast })}^{-1}{(𝑰-𝑨)}^{-1}(𝑰+𝑨)=(𝑰-𝑨){\left[(𝑰-𝑨)(𝑰-{𝑨}^{\ast })\right]}^{-1}(𝑰+𝑨)\Rightarrow }$
   ${\displaystyle {𝑪}^{\ast }𝑪=(𝑰-𝑨){\left[(𝑰+𝑨)(𝑰-𝑨)\right]}^{-1}(𝑰+𝑨)=(𝑰-𝑨){(𝑰-𝑨)}^{-1}{(𝑰+𝑨)}^{-1}(𝑰+𝑨)=𝑰.}$