Singular Value Decomposition

1 What is SVD?

For any $A\in {\text{R}}^{m\times n}$ of rank $r$, the (thin) singular‐value decomposition is

$$A=U\mathrm{\Sigma }{V}^T,$$

where

• $U\in {\text{R}}^{m\times r}$ has orthonormal columns ($U^{T}U=I_r$),
• $V\in {\text{R}}^{n\times r}$ has orthonormal columns ($V^{T}V=I_r$),
• $\mathrm{\Sigma }=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_r)$, with ${\sigma }_1\ge \cdots \ge {\sigma }_r>0$.

You can do SO MUCH with this, but rapidly run in to problems of computational cost and numerical stability if you are naive about it.

2 Randomized methods

There are a few mentioned; e.g. everyone name-checks Halko, Martinsson, and Tropp (2010) and Bach et al. (2019). I’ve used Halko, Martinsson, and Tropp (2010) a lot because it is included in PyTorch. I am curious about Allen-Zhu and Li (2017) which claims to be stable at low floating point precision, which is very desirable in these big-network times.

3 Incremental updates / downdates

A rank-1 incremental update corresponds to appending a new column $a\in {\text{R}}^m$ to $A$: Given current SVD $A=U\mathrm{\Sigma }{V}^T$, form

$$A^{\prime }=[Aa]\in {\text{R}}^{m\times (n+1)}.$$

We want $A^{\prime }=U^{\prime }{\mathrm{\Sigma }}^{\prime }{V^{\prime }}^T$ cheaply.

1. Project $a$ onto $\mathrm{span}(U)$:

   $$w=U^{T}a(\in {\text{R}}^r),$$

   and compute the residual

   $$p=a-Uw,\alpha =\parallel p{\parallel }_2.$$

   If $\alpha >0$, set $q=p/\alpha$ (else pick any unit $q\perp U$).

2. Form the small “core”

   $$K=\left[\begin{array}{cc}\mathrm{\Sigma }& w\\ 0& \alpha \end{array}\right]\in {\text{R}}^{(r+1)\times (r+1)}.$$

3. Compute SVD of $K$:

   $$K=\tilde{U}\tilde{\mathrm{\Sigma }}{\tilde{V}}^T,$$

   where $\tilde{U},\tilde{V}\in {\text{R}}^{(r+1)\times (r+1)}$.

4. Update full factors:

   $$U^{\prime }=[Uq]\tilde{U},{\mathrm{\Sigma }}^{\prime }=\tilde{\mathrm{\Sigma }},V^{\prime }=\left[\begin{array}{cc}V& 0\\ 0& 1\end{array}\right]\tilde{V}.$$

Cost: SVD of one $(r+1)\times (r+1)$ matrix instead of $m\times n$.

There are also downdates (removing a column), which are pretty similar.

For fancy variations, there are many papers (Brand 2006, 2002; Bunch and Nielsen 1978; Gu and Eisenstat 1995, 1993; Sarwar et al. 2002; Zhang 2022).

4 …as Frobenius minimiser

TODO.

5 …for PCA

This is nearly trivial but needs spelling out: SVD gives us the PCA, among other useful things.

• Principal Component Analysis

6 Incoming

• Carlo Tomasi’s lecture notes are elegantly pedagogic
• Avrim Blum on SVD
• SVD at Nova Automata

7 References