svd

All matrix is belong to ${\mathbb{R}}^{m\times n}$ if not specified.

1. SVD

For any matrix $A\in {\mathbb{R}}^{m\times n}$, there exist orthogonal matrices $U\in {\mathbb{R}}^{m\times m}$ and $V\in {\mathbb{R}}^{n\times n}$ such that

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

where $\Sigma \in {\mathbb{R}}^{m\times n}$ is a rectangular diagonal matrix whose diagonal entries are the singular values of $A$:

$${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0,$$

and $r=rank(A)$. Equivalently, the compact form of the SVD is

$$A=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T.$$

Here, ${\sigma }_i=\sqrt{{\lambda }_i}$, where ${\lambda }_i$ is a non-zero eigenvalue of both $A^{T}A$ and $A{A}^T$; $v_i$ is a corresponding eigenvector of $A^{T}A$, and

$$u_i=\frac{1}{{\sigma }_i}A{v}_i$$

is a corresponding eigenvector of $A{A}^T$.

2. Preliminaries

$B=A^{T}A\in {\mathbb{R}}^{n\times n}$ is a symmetric matrix, so it is diagonalizable, and the eigenvalues are non-negative.

$C=A{A}^T\in {\mathbb{R}}^{m\times m}$ is also a symmetric matrix, so it is diagonalizable, and the eigenvalues are non-negative.

$B=V{\Lambda }_B{V}^T,V\in {\mathbb{R}}^{n\times n}$

$C=U{\Lambda }_C{U}^T,U\in {\mathbb{R}}^{m\times m}$

2.1. proposition

$B$ and $C$ have the same non-zero eigenvalues with the same multiplicity(geometric multiplicity).

proof

$$\begin{array}{c}Bv=A^{T}Av=\lambda v⟹\\ CAv=A{A}^{T}Av=\lambda Av\end{array}$$

if $\lambda$ is an eigenvalue of $B$, then it is also an eigenvalue of $C$.
similarly,

$$\begin{array}{c}Cv=A{A}^{T}v=\lambda v⟹\\ B{A}^{T}v=A^{T}A{A}^{T}v=\lambda A^{T}v\end{array}$$

if $\lambda$ is an eigenvalue of $C$, then it is also an eigenvalue of $B$.
so $B$ and $C$ have the same eigenvalues.
we analyze the geometric multiplicity of the non-zero eigenvalues.

$$v\in Ker(A^{T}A-\lambda I)⟺Bv=A^{T}Av=\lambda v⟹$$ $$CAv=A{A}^{T}Av=\lambda Av⟺Av\in Ker(A{A}^T-\lambda I)$$

consider the linear map:

$$\begin{array}{c}f:Ker(A^{T}A-\lambda I)\to Ker(A{A}^T-\lambda I)\\ f(v)=Av\end{array}$$

if $f(v)=Av=\lambda v=0$, because $\lambda \ne 0$, so $v=0$.
so $f$ is injective.
for any $w\in Ker(A{A}^T-\lambda I)$, there exists $v=(1/\lambda )A^{T}w\in Ker(A^{T}A-\lambda I)$ such that $f(v)=A(1/\lambda )A^{T}w=(1/\lambda )A{A}^{T}w=(1/\lambda )\lambda w=w$.
so $f$ is surjective.
so $f$ is an isomorphism.
Therefore, $B$ and $C$ have the same non-zero eigenvalues with the same geometric multiplicity.

2.2. proposition

$$Ker(A)=Ker(A^{T}A)$$

proof

$$x\in Ker(A)⟺Ax=0⟹A^{T}Ax=0⟺x\in Ker(A^{T}A)$$ $$x\in Ker(A^{T}A)⟺A^{T}Ax=0⟹x^T{A}^{T}Ax=0⟹Ax=0⟺x\in Ker(A)$$

Therefore, $Ker(A)=Ker(A^{T}A)$.

3. Construction and proof

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

$V=(v_1,v_2,\cdots ,v_n)$

$U=(u_1,u_2,\cdots ,u_m)$

$U=(u_1,u_2,\cdots ,u_m):=((1/\sqrt{{\lambda }_1})A{v}_1,(1/\sqrt{{\lambda }_2})A{v}_2,\cdots ,(1/\sqrt{{\lambda }_r})A{v}_r,u_{r+1},\cdots ,u_m)$

$\Sigma =\left[\begin{array}{cc}diag(\sqrt{{\lambda }_1},\sqrt{{\lambda }_2},\cdots ,\sqrt{{\lambda }_r}),& 0\\ 0,& 0\end{array}\right]$

${\lambda }_i$ is the eigenvalue of $B$ and $C$. ${\lambda }_i\ge {\lambda }_{i+1}$

$v_i$ is the eigenvector of $B=A^{T}A$, and $(v_i{)}_{i=r+1}^n$ belongs to $Ker(A^{T}A)$

$u_i$ is the eigenvector of $C=A{A}^T$

$$\begin{array}{rl}U\Sigma V^T& =\sum _{i=1}^r\sqrt{{\lambda }_i}{u}_i{v}_i^T\\ & =\sum _{i=1}^r\sqrt{{\lambda }_i}((1/\sqrt{{\lambda }_i})A{v}_i)v_i^T\\ & =\sum _{i=1}^{r}A{v}_i{v}_i^T\\ & =A\sum _{i=1}^r{v}_i{v}_i^T\end{array}$$

It is need to prove that $A{\sum }_{i=1}^r{v}_i{v}_i^T=A$

$$\forall x=(x_1,x_2,\cdots ,x_n{)}^T\in {\mathbb{R}}^n,x=\sum _{i=1}^n{\alpha }_i{v}_i$$

$v_i^{T}x=v_i^T{\sum }_{i=1}^n{\alpha }_i{v}_i={\alpha }_i$

$$x=\sum _{i=1}^n{\alpha }_i{v}_i=\sum _{i=1}^n(v_i^{T}x)v_i$$ $$\begin{array}{r}\forall x,A\sum _{i=1}^r{v}_i{v}_i^{T}x=A\sum _{i=1}^r{v}_i{v}_i^{T}x+A\sum _{i=r+1}^n{v}_i{v}_i^{T}x=Ax⟹A\sum _{i=1}^r{v}_i{v}_i^T=A\end{array}$$

Therefore, $A=U\Sigma V^T={\sum }_{i=1}^r\sqrt{{\lambda }_i}{u}_i{v}_i^T$

let ${\sigma }_i=\sqrt{{\lambda }_i}$, then $A={\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^T$