Singular Value Decomposition

Abstract

Singular Value Decomposition is a way of decomposing any matrix and more powerful than eigen value decomposition or spectral decomposition.

Miscellaneous Facts about Matrices and Decomposition

Gilbert Strang: The Four Fundamental Subspaces: 4 Lines

In Eigenvalue Decomposition, A is diagonalized as $A=U\Lambda U^T$. There are three big problems when it comes to this decomposition.

• The matrix must be a square matrix
• The matrix must be diagonalizable. (must have a complete set of eigenvectors)
• The eigenvectors are not orthogonal (problem for spectral decomposition)

The above conditions are always met for Symmetric Matrices ($A=A^T$) and Normal Matrices ($A{A}^T=A^{T}A$)

🔺 Solution: Singular Vectors | Singular Value Decomposition

---

Singular Value Decomposition

Suppose $A\in R^{m\times n}$

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

There are two sets of singular vectors. For eigenvectors, we only have one.

U = left singular vector $U\in R^{m\times m}$ $A{A}^T$ V = right singular vector $V\in R^{n\times n}$ = eigenvectors of $A^{T}A$ $\Sigma$ = diag (${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r$)

$A^{T}A$ is symmetric, square (n x n), positive semi definite (can be proven using norm property).

$$A^{T}A=V\Sigma V^T\in R^{n\times n}$$ $$A{A}^T=U\Sigma U^T\in R^{m\times m}$$ $$A^{T}A=V{\Sigma }^T{U}^{T}U\Sigma V=V({\Sigma }^T\Sigma )V$$ $$A{A}^T=U\Sigma V^{T}V{\Sigma }^T{U}^T=U(\Sigma {\Sigma }^T)U^T$$

Attention

• $A^{T}A\text{ and }A{A}^T$ has same eigenvalues.
• $\sigma$ is the $\sqrt{\lambda (A^{T}A\text{ or }A{A}^T)}$
• $V\in {\mathbf{R}}^n$ is the eigenvector of $A^{T}A$.
• $U\in {\mathbf{R}}^m$ is the eigenvector of $A{A}^T$.
• $U_r{U}_r^T$ is the projection onto R(A), Column Space of A
• $U_{m-r}{U}_{m-r}^T=U_{\perp }{U}_{\perp }^T$ is the projection onto $N(A^T)=R(A{)}^{\perp }=$ left null space of A
• $V_r{V}_r^T$ is the projection onto $R(A^T)=N(A{)}^{\perp }=\text{Row Space of A}$
• $V_{n-r}{V}_{n-r}^T=V_{\perp }{V}_{\perp }^T$ is the projection onto $N(A)=\text{ Null Space of A}$

v_r lives in the row space and null space of A. u_r lives in the column space and left null space of A.

v's and u's are orthogonal since $A{A}^T$ and $A^{T}A$ are symmetric matrices.

$$A\left[\begin{array}{c}{v}_1\dots v_r\end{array}\right]=\left[\begin{array}{c}{u}_1\dots u_r\end{array}\right]\left[\begin{array}{ccc}{\sigma }_1& & \\ & \ddots & \\ & & {\sigma }_r\end{array}\right]$$ $$A{v}_i={\sigma }_i{u}_i$$ $$\text{Thus, }{u}_i=\frac{A{v}_i}{{\sigma }_i}\text{and these u are orthogonal}$$

A can also be written as sum of rank one matrices with $\sigma$ determining the “importance / contribution” of that rank-one matrix (dyad).

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

When are U and V the same?

U and V are the same when they’re equal to Q, where Q is the eigenvector matrix of A. When A is Symmetric and Positive Semi Definite , A can be decomposed using spectral theorem as $A=Q\Lambda Q^T$. Then, we can see that $\mathbf{U}=\mathbf{V}$ will be the same and the $\lambda$ is $\sigma$.

---