Singular Value Decomposition

Definition

${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times n}{\mathbf{D}}_{n\times m}({\mathbf{V}}_{m\times m}{)}^{⊺}={\sum }_{i=1}^{\min (n,m)}{d}_i{U}_i{V}_i^{⊺}$ An arbitrary matrix ${\mathbf{A}}_{n\times m}$ can be decomposed to $\mathbf{UD}{\mathbf{V}}^{⊺}$.

For $n\ge m$ ${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times m}{\mathbf{D}}_{m\times m}({\mathbf{V}}_{m\times m}{)}^{⊺}$ where ${\mathbf{U}}^{⊺}\mathbf{U}={\mathbf{I}}_m$ and ${\mathbf{V}}^{⊺}\mathbf{V}=\mathbf{V}{\mathbf{V}}^{⊺}={\mathbf{I}}_m$ and $\mathbf{D}$ is Diagonal Matrix

For $n\le m$ ${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times n}{\mathbf{D}}_{n\times n}({\mathbf{V}}_{m\times n}{)}^{⊺}$ where ${\mathbf{U}}^{⊺}\mathbf{U}=\mathbf{U}{\mathbf{U}}^{⊺}={\mathbf{I}}_n$ and ${\mathbf{V}}^{⊺}\mathbf{V}={\mathbf{I}}_n$ and $\mathbf{D}$ is Diagonal Matrix

Calculation

For matrix ${\mathbf{A}}_{m\times n}=\mathbf{UD}{\mathbf{V}}^{⊺}$

${\mathbf{V}}_{n\times n}$ is the matrix of orthonormal eigenvectors of ${\mathbf{A}}^{⊺}\mathbf{A}$ ${\mathbf{U}}_{m\times m}$ is the matrix of orthonormal eigenvectors of $\mathbf{A}{\mathbf{A}}^{⊺}$ ${\mathbf{D}}_{m\times n}$ is the Diagonal Matrix made of the square roots of the non-zero eigenvalues of ${\mathbf{A}}^{⊺}\mathbf{A}$ and $\mathbf{A}{\mathbf{A}}^{⊺}$ sorted in descending order.

If the eigendecomposition is ${\mathbf{A}}^{⊺}\mathbf{Ax}=\lambda \mathbf{x}$, then the eigenvalues $\lambda \ge 0$ and the eigenvectors $\mathbf{x}\in \mathbb{C}({\mathbf{A}}^{⊺})$ are orthonormal by Spectral Theorem. If the $\mathrm{rank}(\mathbf{A})=r\le n$, then ${\lambda }_1⪈{\lambda }_2⪈\cdots \ge {\lambda }_r,{\lambda }_{r+1}=\dots {\lambda }_n=0$. Where ${\sigma }_i=\sqrt{{\lambda }_i}{}_{i=1,2,\dots ,r}$ are called the singular values.

Now, the Orthonormal Matrix $\mathbf{V}=[{\mathbf{V}}_1,{\mathbf{V}}_2]$ is calculated using the singular values. Where $V_1=[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_r]$ is the Orthonormal Matrix of eigenvectors corresponding to the non-zero eigenvalues and $V_2=[{\mathbf{v}}_{r+1},{\mathbf{v}}_{r+2},\dots ,{\mathbf{v}}_n]$ is the Orthonormal Matrix of eigenvectors corresponding to zero eigenvalues where each ${\mathbf{v}}_r+i\in \mathbf{N}({\mathbf{A}}^{⊺}\mathbf{A})=\mathbf{N}(\mathbf{A})$, and ${\mathbf{D}}_{m\times n}=\mathrm{diag}({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r,0,\dots ,0)$ is a rectangular Diagonal Matrix.

Since $\mathbf{V}$ is an orthonormal matrix and $\mathbf{D}$ is a Diagonal Matrix, $\mathbf{AV}=\mathbf{UD}\Rightarrow \mathbf{A}[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n]=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_m]\mathbf{D}\Rightarrow \mathbf{A}{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i\Rightarrow {\mathbf{u}}_i=\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$. Now, the Orthonormal Matrix $\mathbf{U}=[{\mathbf{U}}_1,{\mathbf{U}}_2]$ is calculated using the linear system $\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$ and the null space of $\mathbf{A}$, $\mathbf{N}(\mathbf{A})$ Where ${\mathbf{U}}_1=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_r]$ is the Orthonormal Matrix of the vectors ${\mathbf{u}}_{\{1,2,\dots ,r\}}\in \mathbf{C}(\mathbf{A})$ obtained from the system equation $\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$ And ${\mathbf{U}}_2=[{\mathbf{u}}_{r+1},{\mathbf{u}}_{r+2},\dots ,{\mathbf{u}}_m]$ is the Orthonormal Matrix of the vectors ${\mathbf{u}}_{\{r+1,r+2,\dots ,m\}}\in \mathbf{N}({\mathbf{A}}^{⊺})$. which is corresponding to zero eigenvalues

The Orthonormal Matrix $\mathbf{U}=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_m]$ can also be formed by the eigenvectors of $\mathbf{A}{\mathbf{A}}^{⊺}$ similarly to calculating of $\mathbf{V}$.

Facts

$\mathbf{U},\mathbf{V}$ are the Unitary Matrix

Let $\mathbf{A}$ be a real symmetric Positive Semi-Definite Matrix Then, the Eigendecomposition(Spectral Decomposition) of $\mathbf{A}$ and the singular value decomposition of $\mathbf{A}$ are equal.

$\mathbf{A}=\mathbf{P\Lambda }{\mathbf{P}}^{⊺}=\mathbf{UD}{\mathbf{V}}^{⊺}$ where $\mathbf{P}=\mathbf{U}=\mathbf{V}$ and $\mathbf{\Lambda }=\mathbf{D}$ are non-negative and the shape of the every matrix is $n\times n$

Visualization

every matrix can be decomposed as a

• ${\mathbf{V}}^{⊺}$: rotation and reflection
• $\mathbf{D}$: scaling
• $\mathbf{U}$: rotation and reflection