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 AA is symmetric

A⋅(q1,…qn)=(λ1q1…λnqn)=(q1⋯qn)⋅(λ1⋯⋯⋮⋱⋮⋯λn⋯)\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 AA is symmetric, the eigenvectors QQ of AA would be orthogonal. And Q−1=Q⊤Q^{-1} = Q^{\top} for orthogonal matrix. Then we get the SVD as below:

AQ=Qλ→A=QλQ−1=QλQ⊤\begin{aligned} AQ=Q \lambda \quad \rightarrow \quad A=Q \lambda Q^{-1}=Q \lambda Q^{\top} \end{aligned}

Matrix AA isn’t symmetric

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

(1) n right singular vectors, v1,⋯ ,vnv_{1}, \cdots , v_{n} orthogonal in RnR^n

(2) m left singular vectors, u1,⋯ ,unu_{1}, \cdots , u_{n} orthogonal in RmR^m

If A=UΣV⊤A=U \Sigma V^{\top}, then
A⊤A=(UΣV⊤)⊤(UΣV⊤)=V⊤Σ⊤U⊤UΣV⊤=VΣ⊤ΣV⊤→n×nA^{\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

Σ⊤Σ=(σ1⋱σn)(σ1⋱σn)=(σ12⋱σn2)\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)

→(σ12⋯σn2)\rightarrow\left(\sigma_{1}{ }^{2} \cdots \sigma_{n}{ }^{2}\right) are eigenvalues of A⊤AA^{\top} A

AA⊤=(UΣV⊤)(UΣV⊤)⊤=UΣV⊤V⊤Σ⊤U⊤=UΣΣ⊤U⊤→m×mA 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

ΣΣ⊤=(σ1⋱σm)(σ1⋱σm)=(σ12⋱σm2)\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)

→(σ12⋯σm2)\rightarrow\left(\sigma_{1}^{2} \cdots \sigma_{m}^{2}\right) are eigenvalues of AA⊤A A^{\top}

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

Example

A=(104601),A⊤A=(17242437),AA⊤=(1404526061)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⊤AA^{\top} A

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

Eigenvectors: v1=(0.550.83),v2=(−0.830.55)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⊤A⋅(0.55−0.830.830.55)=(0.55−0.830.830.55)⋅(53001)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 AA⊤A A^{\top}

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

Eigenvectors: u1=(0.080.990.11),u2=(−0.8300.56),u3=(−0.550.14−0.82)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⊤AA^{\top}A and AA⊤AA^{\top} from large to small: σ1=53,σ2=1\sigma_{1}=\sqrt{53}, \quad \sigma_{2}=1

A=UΣV⊤=(0.08−0.83−0.550.9900.140.110.56−0.82)⋅(5300100)⋅(0.550.83−0.830.35)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

1
2
3
4
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)

All articles in this blog adopt the CC BY-SA 4.0 agreement except for special statements. Please indicate the source for reprinting!