Faster Low-rank Approximation using Adaptive Gap-based Preconditioning

Alon Gonen, Shai Shalev-Shwartz

We propose a method for rank $k$ approximation to a given input matrix $X\in {\mathbb{R}}^{d\times n}$ which runs in time \[ \tilde{O} \left(d ~\cdot~ \min\left\{n + \tilde{sr}(X)…