Superfast Low Rank Approximation of a Matrix

We propose superfast (aka sublinear cost) algorithms for (i) computation and (ii) iterative refinement of a Low Rank Approximation (LRA) of a matrix. A superfast algorithm only accesses a small fraction of all entries of a matrix and for a worst-case input cannot output its close LRA or even verify whether a fixed candidate matrix is indeed a close LRA. Nevertheless, we first recall some well-known algorithms that solve these problems in linear or super-linear time and then propose their superfast modifications, which promise to succeed for a large class of real-world matrices according to our analysis and numerical tests.