Singular Value Decomposition
Singular Value Decomposition (SVD) is a matrix factorization method that is applicable to all matrices, including rectangular ones (unlike Eigen-decomposition, for example).
$$
\begin{aligned}
A=U \Sigma V^{\mathbf{T}}=\left[\begin{array}{ccc}
1 & \mid & \mid \\
\boldsymbol{u}_1 & \boldsymbol{u}_2 & \boldsymbol{u}_3 \\
\mid & \mid & \mid
\end{array}\right]\left[\begin{array}{cc}
\sigma_1 & \\
& \sigma_2 \\
&
\end{array}\right]\left[\begin{array}{c}
-\boldsymbol{v}_1^{\mathbf{T}}- \\
-\boldsymbol{v}_2^{\mathbf{T}}-
\end{array}\right] & =\sigma_1\left[\begin{array}{c}
\mid \\
\boldsymbol{u}_1 \\
\mid
\end{array}\right]\left[-\boldsymbol{v}_1^{\mathbf{T}}-\right]+\sigma_2\left[\begin{array}{c}
\mid \\
\boldsymbol{u}_2 \\
\mid
\end{array}\right]\left[-\boldsymbol{v}_2^{\mathbf{T}}-\right] \\
& =\sigma_1 \boldsymbol{u}_1 \boldsymbol{v}_1^{\mathbf{T}}+\sigma_2 \boldsymbol{u}_2 \boldsymbol{v}_2^{\mathbf{T}}
\end{aligned}
$$
where:
- $A \in \mathbb{R}^{m \times n}$
- $U \in \mathbb{R}^{m \times m}$ and $V \in \mathbb{R}^{n \times n}$ are orthogonal matrices
- $\Sigma = \text{diag}(\sigma_1, \ldots, \sigma_p) \in \mathbb{R}^{m \times n}$ where $p = \min(m,n)$
- $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_p \geq 0$ (singular values in descending order)
Instead of seeing the matrix as a mess of numbers, SVD reveals that any matrix is really just:
- A rotation/reflection ( $V^T$ )
- Followed by pure stretching along perpendicular axes ( $\Sigma$ )
- Followed by another rotation/reflection ( $U$ )
This is the "simplest possible" way to understand what any linear transformation actually does.
Low Rank
$$
A_k=U D_k V^T, \quad D_k=\operatorname{diag}\left(\sigma_1, \ldots, \sigma_k, 0, \ldots, 0\right) .
$$
Truncating the matrix A $k<r$ terms gives the best rank- $k$ approximation to $A$ in both the 2 -norm and the Frobenius norm.
Eigen values
Any $n \times m$ matrix $\mathbf{A}$ can be written as
$$
\mathbf{A}=\mathbf{U \Sigma V}^T,
$$
where
$$
\begin{array}{ll}
\mathbf{U}=\text { eigenvectors of } \mathbf{A A}^T & n \times n \\
\Sigma=\sqrt{\operatorname{diag}\left(\operatorname{eig}\left(\mathbf{A} \mathbf{A}^T\right)\right)} & n \times m \\
\mathbf{V}=\text { eigenvectors of } \mathbf{A}^T \mathbf{A} & m \times m
\end{array}
$$
References
- The Art of Linear Algebra, Kenji Hirannbe 2021
- https://www.cs.princeton.edu/~smattw/Teaching/Fa19Lectures/lec11/lec11.pdf