singular value decomposition

Singular Value Decomposition (SVD)

$$X=\left[\begin{array}{cccc}|& |& & |\\ x_1& x_2& \cdots & x_m\\ |& |& & |\end{array}\right]=U\Sigma V^T=\left[\begin{array}{cccc}|& |& & |\\ u_1& u_2& \cdots & u_n\\ |& |& & |\end{array}\right]\left[\begin{array}{cccc}{\sigma }_1& & & \\ & {\sigma }_2& & \\ & & \ddots & \\ & & & {\sigma }_m\\ 0& \dots & ⋮& 0\end{array}\right]{\left[\begin{array}{cccc}|& |& & |\\ v_1& v_2& \cdots & v_m\\ |& |& & |\end{array}\right]}^T$$

where $x_k\in {\mathbb{R}}^n$ denote the columns of $X\in {\mathbb{R}}^{n\times m}$, which can be any data flattened into $n\times 1$ column vectors.
For example the individual $x_k$ could be an image, or a snapshot of some physical process through time.

$U\in {\mathbb{R}}^{n\times n}$ is called the left singular vectors, $u_k$ are eigenvectors which form the eigenbasis for the column space of $X$. These columns are ordered by the amount of variance they explain in the data (“importance”). They are the principal components of the data containing information about the column space of $X$.
$V\in {\mathbb{R}}^{n\times m}$ is called the right singular vectors. They basically tell us the combination of the left singular vectors that make up each of the original data points ““eigenmixture”” – containing information about the row space of $X$.
$\Sigma \in {\mathbb{R}}^{n\times m}$ is a diagonal matrix containing the singular values ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_m\ge 0$ on the diagonal in descending order ordered by magnitude. They tell us the importance of each singular vector in the decomposition.
$U,V$ are unitary, so $U^{T}U=U{U}^T=I_{n\times n}$ and $V^{T}V=V{V}^T=I_{m\times m}$

This SVD is guaranteed to exist for any matrix $X$ and is unique up to the signs of the singular values, but that doesn’t matter since the vector space is still the same.

“Economy SVD”

A more efficient (and mathematically equivalent) version of the SVD when $n\gg m$ (e.g. when we have a few hundred or thousand megapixel images), where we only compute the meaningful components:

$$X=U\Sigma V^T=\hat{U}\hat{\Sigma }{V}^T$$

where $\hat{U}\in {\mathbb{R}}^{n\times m}$ contains only the first $m$ columns of $U$, $\hat{\Sigma }\in {\mathbb{R}}^{m\times m}$ contain only the first $m$ singular values ¹ , and $V\in {\mathbb{R}}^{m\times m}$ is unchanged; instead of $n$ columns, we only have $m$ columns in $U$ and $\Sigma$ .

We can do this because $X$ only has $m$ linearly independent columns, which means that the remaining columns of $U$ are just linear combinations of the first $m$ columns – the eigenvectors.

While the columns $U_{m+1:}$ are not meaningful for representing $X$, without them, the orthonormal space is not complete ¹, i.e. $U$ is no longer unitary: ${\hat{U}}^T\hat{U}=I_{m\times m},\text{ but }\hat{U}{\hat{U}}^T\ne I$

SVD as Sum of Outer Products

The SVD can be written as a sum of rank-1 ${\mathbb{R}}^{m\times m}$ matrices formed by outer products of corresponding singular vectors, weighted by singular values:

$$\begin{array}{rl}X& =U\Sigma V^T\\ & ={\sigma }_1{u}_1{v}_1^T+{\sigma }_2{u}_2{v}_2^T+\cdots +{\sigma }_m{u}_m{v}_m^T+0\\ & ={\sigma }_1\left[\begin{array}{c}\\ u_1\\ \end{array}\right]\left[\begin{array}{ccc}& v_1^T& \end{array}\right]+{\sigma }_2\left[\begin{array}{c}\\ u_2\\ \end{array}\right]\left[\begin{array}{ccc}& v_2^T& \end{array}\right]+\cdots +{\sigma }_m\left[\begin{array}{c}\\ u_m\\ \end{array}\right]\left[\begin{array}{ccc}& v_m^T& \end{array}\right]\end{array}$$

Each term ${\sigma }_k{u}_k{v}_k^T$ is a rank-1 matrix by construction, fully depending on / explained by one row and col, and captures a fundamental (orthogonal) direction of variation in the data, weighted by the corresponding singular value ${\sigma }_k$.

This sum of rank-1 matrices increasingly improves the approximation of $X$ (like denoising! ²).

Theorem

The ordering by importance allows us to approximate the data matrix $X$ by truncating the singular value matrix $\Sigma$ to a smaller rank $r$:

$${\sigma }_1{u}_1{v}_1^T+{\sigma }_2{u}_2{v}_2^T+...+{\sigma }_r{u}_r{v}_r^T\approx \tilde{U}\tilde{\Sigma }{\tilde{V}}^T$$

The Eckard-Young Theorem tells us that the best possible approximation with a given rank $r$ is exactly this truncation of the SVD:

$${\text{argmin}}_{\tilde{X}:\text{ st rank}(\tilde{X})=r}||X-\tilde{X}|{|}_F=\tilde{U}\tilde{\Sigma }{\tilde{V}}^T$$

$\mid \cdot {\mid }_F$ is the frobenius norm (sqrt of the sum of squares of all elements).

Intuitive interpretation: $X^{T}X=V\hat{\Sigma }{\hat{U}}^T\hat{U}\hat{\Sigma }{V}^T=V{\hat{\Sigma }}^2{V}^T⟹X^{T}XV=V{\hat{\Sigma }}^2$

$X=\hat{U}\Sigma V^T⟹X^T=V\hat{\Sigma }{\hat{U}}^T$
$X^{T}X=V\hat{\Sigma }\text{cancelto}I{\hat{U}}^T\hat{U}\hat{\Sigma }{V}^T=V{\hat{\Sigma }}^2{V}^T$ ($\hat{U}$’s columns are still orthogonal)
This is a diagonalization of $X^{T}X$ with the eigenvectors $V$ and eigenvalues ${\sigma }_i^2$!
→ The columns of $V$ are the eigenvectors of the second moment column-wise “correlation matrix” $X^{T}X$ and the singular values are the square roots of the eigenvalues of $X^{T}X$, quantifying the importance of each eigenvector for the correlation matrix.
Similarly for $X{X}^T=\hat{U}\hat{\Sigma }{V}^{T}V\hat{\Sigma }{\hat{U}}^T=\hat{U}{\hat{\Sigma }}^2{\hat{U}}^T$.
→ The columns of $U$ are the eigenvectors of the second moment row-wise “correlation matrix” $X{X}^T$.

Computing the SVD through Eigendecomposition (extended)

For any matrix $X\in {\mathbb{R}}^{n\times m}$, we can form two symmetric matrices:

$$\begin{array}{rl}{X}^{T}X& =V({\Sigma }^T\Sigma )V^T\in {\mathbb{R}}^{m\times m}\\ X{X}^T& =U(\Sigma {\Sigma }^T)U^T\in {\mathbb{R}}^{n\times n}\end{array}$$

Starting from the SVD $X=U\Sigma V^T$, we can derive how these matrices decompose:

$$\begin{array}{rl}{X}^{T}X& =(U\Sigma V^T{)}^T(U\Sigma V^T)\\ & =V{\Sigma }^T{U}^{T}U\Sigma V^T\\ & =V{\Sigma }^T\Sigma V^T\\ & =V\left[\begin{array}{ccc}{\sigma }_1^2& & \\ & \ddots & \\ & & {\sigma }_m^2\end{array}\right]V^T\end{array}$$

Which now looks like an eigendecomposition of $X^{T}X$ with eigenvectors $V$ and eigenvalues ${\sigma }_i^2$.
Similarly for $X{X}^T$:

$$\begin{array}{rl}X{X}^T& =(U\Sigma V^T)(U\Sigma V^T{)}^T\\ & =U\Sigma V^{T}V{\Sigma }^T{U}^T\\ & =U\Sigma {\Sigma }^T{U}^T\\ & =U\left[\begin{array}{ccc}{\sigma }_1^2& & \\ & \ddots & \\ & & {\sigma }_m^2\end{array}\right]U^T\end{array}$$

Taking square roots of these eigenvalues gives us the singular values: ${\sigma }_i=\sqrt{{\lambda }_i}$.
This is of course not a practical way to compute the SVD.

If $X$ is symmetric and positive semidefinite, then $U=V$, i.e. SVD equals eigendecomposition.

SVDs are a data-driven generalization of fourier transforms, where the unitary matrices are rotating a coordinate transformation of the data into another coordinate system where things are simpler (principle directions that explain most of the column / row space).

Geometric interpretation:
$\Sigma$ turns the unitary matrix $U$ into an ellipsoid (stretching /squishing).
$U$ is the part that rotates the data (and potentially squashes it onto lower dimensions).

The SVD allows us to generalize solving linear systems of equations $Ax=b$ to nonsquare $A$ matrices.

$\text{row}(A)=\text{col}(V)$

Referencces

SVD - Data-Driven Science and engineering - Steve Brunton
Visual Kernel

Footnotes

1. For $\Sigma$ this is simply omitting the zero padding which was only necessary to be able to multiply $U\Sigma$ and cancelled these columns of $U$ anyways. ↩

2. You can think of denoising with the SVD as the “reverse” process, approximating the clean signal: For a noisy data matrix $X=X_{\text{clean}}+X_{\text{noise}}$, we omit smaller singular values not to compress, but because the noise typically contributes more to smaller singular values and has less structured patterns than the true signal. ↩