SVD

1. Work out again the SVD theorem done in the class:
   If $A$ is a real $m \times n$ matrix then here exist orthogonal matrices
       and $${\bf V} = \left[{\bf v_1},\ldots,{\bf v_n}\right] \in \mathbb{R}^{n \times n}$$
   such that
   $${\bf A} = {\bf U}{\bf\Sigma}{\bf V}^T$$
   where
   $${\bf\Sigma} = diag(\sigma_1,\sigma_2,\ldots,\sigma_p) \;\;\;p = min\{m,n\}$$
   and $\sigma_1 \geq \sigma_2 \geq \ldots \geq \sigma_p$.
2. Suppose that $\sigma_1 \geq \sigma_2 \geq \ldots \geq \sigma_r > \sigma_{r+1} = \ldots = \sigma_p = 0$. Then show that
   1. $rank({\bf A}) = r$
   2. $null({\bf A}) = \left[{\bf v_{r+1}},\ldots,{\bf v_n}\right]$
   3. $range({\bf A}) = \left[{\bf u_1},\ldots,{\bf u_r}\right]$
   4. If ${\bf U_r} = {\bf U}(:,1:r)$, ${\bf\Sigma_r} = {\bf\Sigma}(1:r,1:r)$ and ${\bf V_r} = {\bf V}(:,1:r)$, then
      $${\bf A_r} = {\bf U_r}{\bf\Sigma_r}{\bf V_r}^T = \sum_{i=1}^r \sigma_i {\bf u_i}{\bf v_i}^T$$

3. Show that
   1. $\Vert{\bf A}\Vert _F^2 = \sigma_1^2 + \sigma_2^2 + \ldots + \sigma_p^2$
   2. $\Vert{\bf A}\Vert _2^2 = \sigma_1$
4. Let the SVD of ${\bf A}$ be as above. If $k < r = rank({\bf A})$ and
   $${\bf A_k} = \sum_{i=1}^k \sigma_i {\bf u_i}{\bf v_i}^T$$
   then show that
   $$\min_{rank({\bf B} = k)} \Vert{\bf A} - {\bf B}\Vert _2^2 = \Vert{\bf A} - {\bf A_k}\Vert _2^2 = \sigma_1$$

5. Show (without using condition numbers) that if ${\bf A}$ is square ( $n \times n$) and $\sigma_n > 0$ is small, then solving ${\bf x} =$A $^{-1}{\bf b}$ is unstable.
6. Show that in the $\Vert\;\Vert _2$ norm
   $$cond({\bf A}) = \frac{\sigma_1}{\sigma_n}$$