Error Estimation for Sketched SVD via the Bootstrap
Error Estimation for Sketched SVD via the Bootstrap
复制标题
DOI：
--
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Miles E. Lopes;N. Benjamin Erichson;Michael W. Mahoney
中科院分区：
文献类型：
--
作者：
Miles E. Lopes;N. Benjamin Erichson;Michael W. Mahoney
为了快速计算超大型矩阵的奇异值分解(SVD)的近似，随机化的草图算法已成为一种主流方法。然而，绘制奇异值分解图的一个关键的实际困难是用户不知道所绘制的奇异向量/值与确切的值有多远。事实上，用户可能被迫依赖于分析的最坏情况误差界，这不能解释给定问题的独特结构。因此，缺乏误差估计工具通常会导致比实际需要的计算量大得多的计算。为了克服这些挑战，本文开发了一种完全数据驱动的Bootstrap方法，该方法可以数值估计绘制的奇异向量/值的实际误差。特别是，这允许用户检查粗略的初始SVD的质量，然后自适应地预测需要多少额外的工作才能达到给定的误差容限。此外，该方法在计算上是廉价的，因为它只对绘制的对象进行操作，并且它不需要在被分解的整个矩阵上传递。最后，该方法得到了理论保证和一组非常令人鼓舞的实验结果的支持。
In order to compute fast approximations to the singular value decompositions (SVD) of very large matrices, randomized sketching algorithms have become a leading approach. However, a key practical difficulty of sketching an SVD is that the user does not know how far the sketched singular vectors/values are from the exact ones. Indeed, the user may be forced to rely on analytical worst-case error bounds, which do not account for the unique structure of a given problem. As a result, the lack of tools for error estimation often leads to much more computation than is really necessary. To overcome these challenges, this paper develops a fully data-driven bootstrap method that numerically estimates the actual error of sketched singular vectors/values. In particular, this allows the user to inspect the quality of a rough initial sketched SVD, and then adaptively predict how much extra work is needed to reach a given error tolerance. Furthermore, the method is computationally inexpensive, because it operates only on sketched objects, and it requires no passes over the full matrix being factored. Lastly, the method is supported by theoretical guarantees and a very encouraging set of experimental results.