Matrices with low-rank structure are ubiquitous in scientific computing. Choosing an appropriate rank is a key step in many computational algorithms that exploit low-rank structure. However, estimating the rank has been done largely in an ad-hoc fashion in previous studies. In this work we develop a randomized algorithm for estimating the numerical rank of a matrix. The algorithm is based on sketching the matrix with random matrices from both left and right; the key fact is that with high probability, the sketches preserve the orders of magnitude of the leading singular values. The rank can hence be taken to be the number of singular values of the sketch that are larger than the prescribed threshold. For an $m\times n$ $(m\geq n)$ matrix of numerical rank $r$, the algorithm runs with complexity $O(mn\log n+r^3)$, or less for structured matrices. The steps in the algorithm are required as a part of many low-rank algorithms, so the additional work required to estimate the rank can be even smaller in practice. Numerical experiments illustrate the speed and robustness of our rank estimator.


翻译:低级别结构的矩阵在科学计算中无处不在。 选择合适的等级是许多利用低级别结构的计算算法中的关键一步。 但是, 在以往的研究中, 估计排名基本上是以临时方式完成的。 在这项工作中, 我们开发了一种随机化算法来估计矩阵的数值等级。 算法基于以左、右随机矩阵绘制矩阵图; 关键事实是, 草图以高概率保存领先单数值的大小。 因此, 级别可以被假定为大于规定阈值的素描单值数。 对于一个$m\time n$( m\geq n) 的数字级矩阵来说, $( m\ geq n) 的算法是复杂的 $( mn\ log n+r3) 美元, 或结构化矩阵的算法。 算法中的步骤需要作为许多低级别算法的一部分, 因此, 估计级别所需的额外工作在实践中可以更小一些。 数字性实验显示了我们排名的进度和稳健性。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
已删除
将门创投
6+阅读 · 2019年11月21日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月6日
Arxiv
0+阅读 · 2021年7月5日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
已删除
将门创投
6+阅读 · 2019年11月21日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员