Fast Derandomized Low-rank Approximation and Extensions
For researchers in numerical linear algebra and machine learning, this work offers a theoretical foundation and practical simplification for low-rank approximation methods.
The paper provides formal support for the empirical efficiency of structured random sampling in low-rank approximation, derandomizing and simplifying existing algorithms. Numerical tests confirm the theoretical results.
Low-rank approximation of a matrix by means of structured random sampling has been consistently efficient in its extensive empirical studies around the globe, but adequate formal support for this empirical phenomenon has been missing so far. Based on our novel insight into the subject, we provide such an elusive formal support and derandomize and simplify the known numerical algorithms for low-rank approximation and related computations. Our techniques can be applied to some other areas of fundamental matrix computations, in particular to the Least Squares Regression, Gaussian elimination with no pivoting and block Gaussian elimination. Our formal results and our numerical tests are in good accordance with each other.