Singular Value Decomposition

Its a form of matrix decomposition that decomposes a $m\ast n$ matrix into three distinct matrices.

$$\mathbf{A}=\mathbf{U\Sigma }{\mathbf{V}}^T$$ $$\mathbf{A}=\left[\begin{array}{cccc}|& |& & |\\ {\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_m\\ |& |& & |\end{array}\right]\left[\begin{array}{cccc}{\sigma }_1& & & \\ & {\sigma }_2& & \\ & & \ddots & \\ & & & {\sigma }_n\end{array}\right]\left[\begin{array}{ccc}—& {\mathbf{v}}_1^T& —\\ —& {\mathbf{v}}_2^T& —\\ & ⋮& \\ —& {\mathbf{v}}_n^T& —\end{array}\right]$$

where $U$ is a $m\ast m$ matrix (left singular values), $V$ is a $n\ast n$ matrix (right singular values), $\Sigma$ is a diagonal matrix of eigenvalues in descending order.

Low-Rank Approximation

The best rank-$k$ approximation of a matrix $A$ is given by keeping only the first $k$ largest singular values.

$${\mathbf{A}}_k=\sum _{i=1}^k{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T={\mathbf{U}}_k{\mathbf{\Sigma }}_k{\mathbf{V}}_k^T$$ $$\underset{\text{rank}(\mathbf{B})\le k}{\min }\Vert \mathbf{A}-\mathbf{B}{\Vert }_F=\Vert \mathbf{A}-{\mathbf{A}}_k{\Vert }_F=\sqrt{\sum _{i=k+1}^r{\sigma }_i^2}$$ $$\underset{\text{rank}(\mathbf{B})\le k}{\min }\Vert \mathbf{A}-\mathbf{B}{\Vert }_2=\Vert \mathbf{A}-{\mathbf{A}}_k{\Vert }_2={\sigma }_{k+1}$$

This means that no rank-k matrix can approximate matrix A better than a k-truncated SVD matrix

Applications

• compression
  • can also compress neural network weights!
• noise reduction
• dimensionality reduction

How SVD is decomposed

1. Compute $A^{T}A$

$$\mathbf{M}={\mathbf{A}}^T\mathbf{A}\text{(n × n symmetric positive semidefinite)}$$

2. Find eigendecomposition of $A^{T}A$

$${\mathbf{A}}^T\mathbf{A}=\mathbf{V\Lambda }{\mathbf{V}}^T$$

3. Extract singular values

$${\sigma }_i=\sqrt{{\lambda }_i}$$

4. Compute left singular values

$${\mathbf{u}}_i=\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i\text{for }{\sigma }_i>0$$

5. Assemble the decomposition

$$\mathbf{A}=\mathbf{U\Sigma }{\mathbf{V}}^T$$

Example: Manual Calculation

Let’s compute SVD for a simple 2×2 matrix:

$$\mathbf{A}=\left[\begin{array}{cc}3& 1\\ 1& 3\end{array}\right]$$

Step 1: Compute AᵀA

$${\mathbf{A}}^T\mathbf{A}=\left[\begin{array}{cc}3& 1\\ 1& 3\end{array}\right]\left[\begin{array}{cc}3& 1\\ 1& 3\end{array}\right]=\left[\begin{array}{cc}10& 6\\ 6& 10\end{array}\right]$$

Step 2: Find eigenvalues

$$\det ({\mathbf{A}}^T\mathbf{A}-\lambda \mathbf{I})=\det \left[\begin{array}{cc}10-\lambda & 6\\ 6& 10-\lambda \end{array}\right]=0$$ $$(10-\lambda {)}^2-36=0⟹{\lambda }_1=16,{\lambda }_2=4$$

Step 3: Singular values

$${\sigma }_1=\sqrt{16}=4,{\sigma }_2=\sqrt{4}=2$$

Step 4: Find eigenvectors of AᵀA for V

$${\mathbf{v}}_1=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right],{\mathbf{v}}_2=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right]$$

Step 5: Compute U

$${\mathbf{u}}_1=\frac{1}{{\sigma }_1}\mathbf{A}{\mathbf{v}}_1=\frac{1}{4}\left[\begin{array}{cc}3& 1\\ 1& 3\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]$$ $${\mathbf{u}}_2=\frac{1}{{\sigma }_2}\mathbf{A}{\mathbf{v}}_2=\frac{1}{2}\left[\begin{array}{cc}3& 1\\ 1& 3\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right]$$

Result:

$$\mathbf{A}=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{cc}4& 0\\ 0& 2\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$$

In practice, there are algorithmic implementations in like Numpy and PyTorch that you can use. The way above is not the standard way of doing it because eigendecomposition on very large matrices is very expensive

machineLearning