Fast Randomized Matrix and Tensor Interpolative Decomposition Using CountSketch

01/29/2019
by   Osman Asif Malik, et al.
0

We propose a new fast randomized algorithm for interpolative decomposition of matrices utilizing the CountSketch technique. We then extend our method to the recently proposed tensor interpolative decomposition problem. Theoretical performance guarantees are provided for both the matrix and tensor settings. Numerical experiments on both synthetic and real sparse data demonstrate that our algorithms maintain the accuracy of competing methods, while running in less time, achieving at least an order of magnitude speed-up on large matrices and tensors.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset