Fast randomized matrix and tensor interpolative decomposition using CountSketch

被引：0
作者：
Osman Asif Malik
Stephen Becker
机构：
[1] University of Colorado Boulder,Department of Applied Mathematics
来源：
Advances in Computational Mathematics | 2020年 / 46卷
关键词：
Matrix decomposition; Tensor decomposition; Sketching; 15-02;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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(C), 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 speedup on large matrices and tensors.
引用
收藏
相关论文
共 99 条
[1]  
Ailon N(2009)The fast Johnson–Lindenstrauss transform and approximate nearest neighbors SIAM J. Comput. 39 302-322
[2]  
Chazelle B(2010)Blendenpik: supercharging LAPACK’s least-squares solver SIAM J. Sci. Comput. 32 1217-1236
[3]  
Avron H(2018)A practical randomized CP tensor decomposition SIAM Journal on Matrix Analysis and Applications 39 876-901
[4]  
Maymounkov P(2002)Numerical operator calculus in higher dimensions Proc. Natl. Acad. Sci. 99 10246-10251
[5]  
Toledo S(2006)Algorithms for numerical analysis in high dimensions SIAM J. Sci. Comput. 26 2133-2159
[6]  
Battaglino C(2015)Randomized interpolative decomposition of separated representations J. Comput. Phys. 281 116-134
[7]  
Ballard G(2014)Near-optimal column-based matrix reconstruction SIAM J. Comput. 43 687-717
[8]  
Kolda TG(2017)Optimal CUR matrix decompositions SIAM J. Comput. 46 543-589
[9]  
Beylkin G(2010)Generalizing the column–row matrix decomposition to multi-way arrays Linear Algebra Appl. 433 557-573
[10]  
Mohlenkamp MJ(2004)Finding frequent items in data streams Theoretical Computer Science 312 3-15
12345678910