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.


翻译:我们提出一个新的快速随机算法,用于利用CountSketch对矩阵进行中间分解。然后,我们将这一方法扩大到Biagioni等人(J.Compuut.Phys.281,pp.116-134,2015年)提出的高压分解问题。为矩阵和高压设置提供理论性能保障。合成和真实数据的数值实验表明,我们的算法保持了竞争性方法的准确性,同时在较短的时间内运行,在大型矩阵和高压器上至少实现数量级加速。

0
下载
关闭预览

相关内容

FAST:Conference on File and Storage Technologies。 Explanation:文件和存储技术会议。 Publisher:USENIX。 SIT:http://dblp.uni-trier.de/db/conf/fast/
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
25+阅读 · 2021年4月2日
ICLR 2020会议的16篇最佳深度学习论文
AINLP
5+阅读 · 2020年5月12日
不需要预训练模型的检测算法—DSOD
极市平台
9+阅读 · 2019年10月10日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
TorchSeg:基于pytorch的语义分割算法开源了
极市平台
20+阅读 · 2019年1月28日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【推荐】(TensorFlow)SSD实时手部检测与追踪(附代码)
机器学习研究会
11+阅读 · 2017年12月5日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
Arxiv
0+阅读 · 2022年1月21日
Arxiv
54+阅读 · 2022年1月1日
VIP会员
相关VIP内容
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
25+阅读 · 2021年4月2日
相关资讯
ICLR 2020会议的16篇最佳深度学习论文
AINLP
5+阅读 · 2020年5月12日
不需要预训练模型的检测算法—DSOD
极市平台
9+阅读 · 2019年10月10日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
TorchSeg:基于pytorch的语义分割算法开源了
极市平台
20+阅读 · 2019年1月28日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【推荐】(TensorFlow)SSD实时手部检测与追踪(附代码)
机器学习研究会
11+阅读 · 2017年12月5日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
Top
微信扫码咨询专知VIP会员