首页> 外文期刊>Algorithmica >Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds
【24h】

Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds

机译:低秩矩阵分解的随机算法:尖锐的性能界限

获取原文
获取原文并翻译 | 示例

摘要

The development of randomized algorithms for numerical linear algebra, e.g. for computing approximate QR and SVD factorizations, has recently become an intense area of research. This paper studies one of the most frequently discussed algorithms in the literature for dimensionality reduction-specifically for approximating an input matrix with a low-rank element. We introduce a novel and rather intuitive analysis of the algorithm in [6], which allows us to derive sharp estimates and give new insights about its performance. This analysis yields theoretical guarantees about the approximation error and at the same time, ultimate limits of performance (lower bounds) showing that our upper bounds are tight. Numerical experiments complement our study and show the tightness of our predictions compared with empirical observations.
机译:数值线性代数的随机算法的发展,例如用于计算近似QR和SVD因式分解,最近已成为研究的热点。本文研究了文献中最常讨论的算法之一,用于降维,特别是用于用低秩元素近似输入矩阵。我们在[6]中介绍了对该算法的新颖而直观的分析,这使我们能够得出清晰的估计并给出有关其性能的新见解。该分析为近似误差提供了理论保证,同时,性能的最终极限(下限)表明我们的上限很严格。数值实验对我们的研究起到了补充作用,并且与经验观察结果相比,我们的预测更加严格。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号