Low-rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions
This work addresses the lack of theoretical justification for a widely used empirical technique in matrix computations, benefiting researchers and practitioners in data mining and scientific computing.
The paper provides formal support for the empirical efficiency of low-rank matrix approximation via random sampling with sparse and structured multipliers, promising significant acceleration of fundamental matrix computation and data mining algorithms. Numerical tests confirm the theoretical results.
Low-rank approximation of a matrix by means of random sampling has been consistently efficient in its empirical studies by many scientists who applied it with various sparse and structured multipliers, but adequate formal support for this empirical phenomenon has been missing so far. Our novel insight into the subject leads to such an elusive formal support and promises significant acceleration of the known algorithms for some fundamental problems of matrix computations and data mining and analysis. Our formal results and our numerical tests are in good accordance with each other. We also outline extensions of low-rank approximation algorithms and of our progress to the Least Squares Regression, the Fast Multipole Method, and the Conjugate Gradient algorithms.