Low Rank Interpolative Decomposition
Table of Contents
See: Low Rank Approximation [RandNLA - Section 4]
1. One sided IDs
\begin{align*}
\underset{m\times n}{A} \approx \underset{m \times k} C \times \underset{k \times n} X
\end{align*}
Here, \(A\) is wide \(m << n\) and \(C\) are \(k\) columns of \(A\) and \(X\) is wide interpolation matrix.
\begin{align*} \underset{m\times n}{A} \approx \underset{m \times k} Z \times \underset{k \times n} R \end{align*}Here, \(A\) is tall \(m >> n\) and \(R\) are \(k\) rows of \(A\) and \(Z\) is tall interpolation matrix.
2. Two sided IDs
\begin{align*}
\underset{m\times n}{A} \approx \underset{m \times k} Z \times \underset{k \times k} {A'} \times \underset{k \times n} R
\end{align*}
3. CUR Decomposition
\begin{align*}
\underset{m\times n}{A} \approx \underset{m \times k} {C} \times \underset{k \times k} {U} \times \underset{k \times n} R
\end{align*}
This representation has the benefit that
- sparsity of \(A\) is maintained
- computing \(CUR\) is fast and we need only two passes over \(A\)
For an spectral algorithm to compute CUR see: CUR: Interpolative approximation [Spectral Algorithms.pdf: Page 81]