Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1901.10559 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929641263988736 |
|---|---|
| author | Malik, Osman Asif Becker, Stephen |
| author_facet | Malik, Osman Asif Becker, Stephen |
| contents | We propose a new fast randomized algorithm for interpolative decomposition of matrices which utilizes CountSketch. We then extend this approach to the tensor interpolative decomposition problem introduced by Biagioni et al. (J. Comput. Phys. 281, pp. 116-134, 2015). Theoretical performance guarantees are provided for both the matrix and tensor settings. Numerical experiments on both synthetic and real 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1901_10559 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Fast Randomized Matrix and Tensor Interpolative Decomposition Using CountSketch Malik, Osman Asif Becker, Stephen Numerical Analysis 15-02 We propose a new fast randomized algorithm for interpolative decomposition of matrices which utilizes CountSketch. We then extend this approach to the tensor interpolative decomposition problem introduced by Biagioni et al. (J. Comput. Phys. 281, pp. 116-134, 2015). Theoretical performance guarantees are provided for both the matrix and tensor settings. Numerical experiments on both synthetic and real 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. |
| title | Fast Randomized Matrix and Tensor Interpolative Decomposition Using CountSketch |
| topic | Numerical Analysis 15-02 |
| url | https://arxiv.org/abs/1901.10559 |