10 - SVD

SVD

Let $A\in {\mathbb{R}}^{m\times n}$ be a matrix with $m\ge n$ then

$A$ can be written as

$$A=U\Sigma V^T=\sum _{i=1}^n{\sigma }_i{u}_i{v}_i^T$$

where

$U\in {\mathbb{R}}^{m\times n}$ has orthonormal columns with $U^{T}U=I_n$
$V\in {\mathbb{R}}^{n\times n}$ has orthonormal columns with $V^{T}V=I_n=V{V}^T$ (square orthogonal)
$\Sigma$ is in form

$$\Sigma =\left[\begin{array}{ccc}{\sigma }_1& & \\ & \ddots & \\ & & {\sigma }_n\end{array}\right]=\mathrm{diag}({\sigma }_1,\cdots ,{\sigma }_n)$$

is a diagonal matrix with nonnegative diagonal entries

and $U=[u_1,\cdots ,u_n]$ and $V=[v_1,\cdots ,v_n]$ (columns of $U,V$)

Notation

1. ${\sigma }_i$ are called singular values generally arranged in decreasing order so

$${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n\ge 0$$

2. Columns of $U$ and $V$ are the left and right singular vectors of $A$ respectively

3. Rank of matrix $A$ is number of positive singular values

Proof - Existence

As $A^{T}A\in {\mathbb{R}}^{n\times n}$ is symmetric then

Let $A^{T}Ax=\lambda x$ for $x\ne 0$ then

$$x^T{A}^{T}Ax=\lambda x^{T}x⟹\lambda =\frac{x^T{A}^{T}Ax}{x^{T}x}=\frac{|Ax|}{|x|}>0$$

Hence eigenvalues of $A^{T}A$ are real and non-negative

Let $A^{T}A=V{D}^2{V}^T$ be the symmetric eigenvalue decomposition
where $V\in {\mathbb{R}}^{n\times n}$ orthogonal and $D$ is diagonal

Let $B=AV$ so $B^{T}B=D^2$ is a diagonal matrix so columns of $B$ are pairwise orthogonal
Then $B^{T}B=D^2=\mathrm{diag}({\lambda }_1,\cdots ,{\lambda }_l,0,\cdots ,0)$ where ${\lambda }_l>0$

If $l=n$ then

$$D^{-1}=diag\left(\frac{1}{\sqrt{{\lambda }_1}},\cdots ,\frac{1}{\sqrt{{\lambda }_l}}\right)$$

Let $U:=B{D}^{-1}=AV{D}^{-1}$ with $U^{T}U=I_n$
Let $\Sigma =D$ then

$$A=U\Sigma V^T$$

If $l<n$ then
$B$ has columns which are zero

Let $D_l=\mathrm{diag}({\lambda }_1,\cdots ,{\lambda }_l)$ then

$$B\left[\begin{array}{cc}{D}_l^{-1}& \\ & I_{n-l}\end{array}\right]=\left[\begin{array}{cc}{U}_1& 0\end{array}\right]$$

Hence

$$A=\left[\begin{array}{cc}{U}_1& 0\end{array}\right]\left[\begin{array}{cc}{D}_r& \\ & I_{n-l}\end{array}\right]V^T=\left[\begin{array}{cc}{U}_1& U_2\end{array}\right]\left[\begin{array}{cc}{D}_l& \\ & 0\end{array}\right]V^T$$

where $U_2$ is any orthonormal matrix in orthogonal complement of $U_1$

Let $U=[U_1{U}_2]$ then result follows with $\Sigma =D$