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)