05. Singular Value Decomposition

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$

Link to original

Spectral Norm

For $A\in {\mathbb{R}}^{m\times n}$ then

$$||A|{|}_2={\sigma }_1(A)=\underset{x\ne 0}{\max }\frac{||Ax|{|}_2}{||x|{|}_2}$$

where ${\sigma }_1(A)$ is the largest singular value and using Euclidean Norm so

$$||x|{|}_2=\sqrt{x_1^2+x_2^2+\cdots +x_n^2}$$

Link to original

Low-Rank Approximation

Let $A=U\Sigma V^T$ be the SVD
Let $U=[u_1,\cdots ,u_n]$ and $V=[v_1,\cdots ,v_n]$

Let $r\in \mathbb{N}$ with $r\le n$ then define tall-skinny matrices

$$U_r=[u_1,\cdots ,u_r]\text{ and }{V}_r=[v_1,\cdots ,v_r]\text{ and }{\Sigma }_r=\mathrm{diag}({\sigma }_1,\cdots ,{\sigma }_r)$$

Then define rank-$r$ truncated SVD of $A$ as

$$A_r=U_r{\Sigma }_r{V}_r^T=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T$$

with $\mathrm{rank}(A_r)=r$ and $A_{}$

Link to original

Best Rank- $r$ Approximation Theorem

Let $r\le n$ be an integer

For any $Bin{\mathbb{C}}^{m\times n}$ with $\mathrm{rank}(B)\le r$ then

$$||A-A_r|{|}_2={\sigma }_{r+1}\le ||A-B|{|}_2$$

So truncated SVD $A_r$ is the best rank-$r$ approximant to $A$ in spectral norm

Proof

As

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

with singular values ${\sigma }_{r+1},\cdots ,{\sigma }_n$ along with $r$ $0$s then

$$||A-A_r|{|}_2={\sigma }_{r+1}$$

As $\mathrm{rank}(B)\le r$ then $B=B_1{B}_2^T$ where $B_1,B_2$ have $r$ columns
Hence exists orthonormal null space $W\in {\mathbb{C}}^{n\times (n-r)}$ such that $BW=0$

Then

$$||A-B|{|}_2\ge ||(A-B)W|{|}_2=||AW|{|}_2=||U\Sigma (V^{T}W)|{|}_2$$

As $W$ is $(n-r)$-dimensional and $[v_1,\cdots ,v_{r+1}]$ is the $(r+1)$-dimensional subspace then
Intersection of $W$ and $[v_1,\cdots ,v_{r+1}]$ has non-zero solution for

$$([W,v_1,\cdots ,v_{r+1}])\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=0$$

Let $W{x}_1$ be a solution

Let $x_1$ have unit norm so

$$||U\Sigma V^{T}W{x}_1|{|}_2=||\Sigma V^{T}W{x}_1|{|}_2=||{\Sigma }_{r+1}{y}_1|{|}_2$$

where $||y_1|{|}_2=1$

Then

$$||U{\Sigma }_{r+1}{y}_1||\ge {\sigma }_{r+1}$$

Link to original