Singular Value Decomposition (SVD) Part 2

In Singular Value Decomposition (SVD) Part 1, I introduce one way to calculate SVD. And in this post, I would talk about other ideas about solving SVD.

Matrix $A$ is symmetric

$\begin{aligned} A \cdot\left(q_{1}, \ldots q_{n}\right)&=\left(\lambda_{1} q_{1} \ldots \lambda_{n} q_{n}\right) \\ &=\left(\begin{array}{lll}q_{1} & \cdots & q_{n}\end{array}\right) \cdot\left(\begin{array}{ccc}\lambda_{1} & \cdots & \cdots \\ \vdots & \ddots & \vdots \\ \cdots & \lambda_{n} & \cdots\end{array}\right) \end{aligned}$

When the matrix $A$ is symmetric, the eigenvectors $Q$ of $A$ would be orthogonal. And $Q^{-1} = Q^{\top}$ for orthogonal matrix. Then we get the SVD as below:

$\begin{aligned} AQ=Q \lambda \quad \rightarrow \quad A=Q \lambda Q^{-1}=Q \lambda Q^{\top} \end{aligned}$

Matrix $A$ isn’t symmetric

In big data world, $A$ is a data matrix but it’s not always a square matrix. Under this situation, we can’t work directly with the eigenvectors of $A$, $A^{\top}A$ and $AA^{\top}$ are required for SVD. Then we get “sort of” $\lambda ^{2}$, which are two sets of eigenvectors:

(1) n right singular vectors, $v_{1}, \cdots , v_{n}$ orthogonal in $R^n$

(2) m left singular vectors, $u_{1}, \cdots , u_{n}$ orthogonal in $R^m$

If $A=U \Sigma V^{\top}$, then
$A^{\top} A=\left(U \Sigma V^{\top}\right)^{\top}\left(U \Sigma V^{\top}\right)=V^{\top} \Sigma^{\top} U^{\top} U \Sigma V^{\top}=V \Sigma^{\top} \Sigma V^{\top} \rightarrow n \times n$

$\Sigma^{\top} \Sigma=\left(\begin{array}{llll} \sigma_{1} & & \\ & \ddots & \\ & & \sigma_{n} \end{array}\right)\left(\begin{array}{lll} \sigma_{1} & & \\ & \ddots & \\ & & \sigma_{n} \end{array}\right)=\left(\begin{array}{lll} \sigma_{1}^{2} & & \\ & \ddots & \\ & & \sigma_{n}^{2} \end{array}\right)$

$\rightarrow\left(\sigma_{1}{ }^{2} \cdots \sigma_{n}{ }^{2}\right)$ are eigenvalues of $A^{\top} A$

$A A^{\top}=\left(U \Sigma V^{\top}\right)\left(U \Sigma V^{\top}\right)^{\top}=U \Sigma V^{\top} V^{\top} \Sigma^{\top} U^{\top}=U \Sigma \Sigma^{\top} U^{\top} \rightarrow m \times m$

$\Sigma \Sigma^{\top}=\left(\begin{array}{llll} \sigma_{1} & & \\ & \ddots & \\ & & \sigma_{m} \end{array}\right)\left(\begin{array}{lll} \sigma_{1} & & \\ & \ddots & \\ & & \sigma_{m} \end{array}\right)=\left(\begin{array}{lll} \sigma_{1}^{2} & & \\ & \ddots & \\ & & \sigma_{m}^{2} \end{array}\right)$

$\rightarrow\left(\sigma_{1}^{2} \cdots \sigma_{m}^{2}\right)$ are eigenvalues of $A A^{\top}$

Then in $A=U \Sigma V^{\top}$, $V$ is the eigenvector of $A^{\top}A$, $U$ is the eigenvectors of $AA^{\top}$, the diagonal elements in $\Sigma$ are the root of the first same n non-zero eigenvalues of $A^{\top}A$ and $AA^{\top}$.

Example

$A=\left(\begin{array}{ll} 1 & 0 \\ 4 & 6 \\ 0 & 1 \end{array}\right) \quad, \quad A^{\top} A=\left(\begin{array}{ll} 17 & 24 \\ 24 & 37 \end{array}\right) \quad, \quad A A^{\top}=\left(\begin{array}{ccc}1 & 4 & 0 \\ 4 & 52 & 6 \\ 0 & 6 & 1\end{array}\right)$

For $A^{\top} A$

Eigenvalues: $\lambda_{1}=53, \lambda_{2}=1$

Eigenvectors: $v_{1}=\left(\begin{array}{l}0.55 \\ 0.83\end{array}\right), \quad v_{2}=\left(\begin{array}{c}-0.83 \\ 0.55\end{array}\right)$

$A^{\top} A \cdot\left(\begin{array}{cc}0.55 & -0.83 \\ 0.83 & 0.55\end{array}\right)=\left(\begin{array}{cc}0.55 & -0.83 \\ 0.83 & 0.55\end{array}\right) \cdot\left(\begin{array}{cc}53 & 0 \\ 0 & 1\end{array}\right)$

For $A A^{\top}$

Eigenvalues: $\lambda_{1}=53, \lambda_{2}=1, \lambda_{3}=0$

Eigenvectors: $u_{1}=\left(\begin{array}{l}0.08 \\ 0.99 \\ 0.11\end{array}\right), \quad u_{2}=\left(\begin{array}{c}-0.83 \\ 0 \\ 0.56\end{array}\right), \quad u_{3}=\left(\begin{array}{c}-0.55 \\ 0.14 \\ -0.82\end{array}\right)$

Order the same eigenvalues of $A^{\top}A$ and $AA^{\top}$ from large to small: $\sigma_{1}=\sqrt{53}, \quad \sigma_{2}=1$

$A=U \Sigma V^{\top}=\left(\begin{array}{ccc} 0.08 & -0.83 & -0.55 \\ 0.99 & 0 & 0.14 \\ 0.11 & 0.56 & -0.82 \end{array}\right) \cdot\left(\begin{array}{cc} \sqrt{53} & 0 \\ 0 & 1 \\ 0 & 0 \end{array}\right) \cdot\left(\begin{array}{cc} 0.55 & 0.83 \\ -0.83 & 0.35 \end{array}\right)$

SVD in Python

We can use numpy to construct a matrix in Python. The module linalg in numpy offers many functions of matrix operation

import numpy as np
A = np.array([[1,1],[0,3],[3,0]])
# VT is the Transpose of V, if we want the matrix V, use VT.T
U, Sigma, VT = np.linalg.svd(A, full_matrices=True)