EAGER: Numerical Accuracy of Randomized Algorithms for Matrix Multiplication and Least Squares

PI建议研究矩阵乘法和超定最小二乘问题的随机算法的数值精度和鲁棒性。现有的随机算法的分析主要关注精确算术中的渐近时间和空间复杂度，而对浮点算术中的数值行为知之甚少。 PI提出为矩阵乘法和最小二乘问题的随机算法开发数值扰动和稳定性理论。 这需要发明新的方法和概念来捕捉随机算法的数值行为。 在这种情况下，根本不清楚“数量稳定”是什么意思，更不用说应该如何定义了。如何区分随机化引起的变异性和有限精度引起的变异性？ 应该在哪里考虑失效概率、概率的选择和抽样量等参数？ 回答这些问题的方法包括矩阵扰动分析、概率论和矩阵流形方法。 大量的数值实验将进行证实的分析。随机算法的动机是需要流的海量数据集，太大的传统的确定性算法。 随机算法已经成功地应用于模式识别、社会网络分析、群体遗传学、电路测试和文本分类等应用。 建议的研究将有助于确定哪些应用领域的随机算法是合适的，它也将导致实际的界限和建议的参数选择，以达到用户指定的精度。 拟议的研究是高度相关的，因为随机算法将是不可或缺的exascale计算，在高能物理和天文学等应用中，预计每天都会有peta字节的数据流，而稀有事件检测等任务使得必须很好地理解数值精度和鲁棒性。

The PI proposes to investigate the numerical accuracy and robustness of randomized algorithms for matrix multiplication and overdetermined least squares problems. Existing analyses of randomized algorithms are mostly concerned with asymptotic time and space complexity in exact arithmetic, and very little is known about their numerical behavior in floating point arithmetic. The PI proposes to develop a numerical perturbation and stability theory for randomized algorithms for matrix multiplication and least squares problems. This entails the invention of new approaches and concepts to capture the numerical behavior of randomized algorithms. It is not at all clear what ``numerical stability'' means in this context, let alone how it should be defined. How does one distinguish variability caused by randomization from variability caused by finite precision? Where should parameters like failure probability, choice of probabilities, and amount of sampling be accounted for? Proposed approaches for answering these questions will include matrix perturbation analysis, probability theory, and methods on matrix manifolds. Extensive numerical experiments will be performed to corroborate the analyses.The motivation for randomized algorithms is the need for streaming massive data sets that are too large for traditional deterministic algorithms. Randomized algorithms have been implemented successfully for applications such as pattern recognition, social network analysis, population genetics, circuit testing, and text classification. The proposed research will help to determine for which application domains a randomized algorithm is suitable, and it will also result in practical bounds and recommendations for parameter choices to achieve a user-specified accuracy. The proposed research is highly relevant because randomized algorithms will be indispensable for exascale computing, in applications like high energy physics and astronomy, where peta bytes of data are expected to stream in daily and tasks like rare event detection make it imperative to have a good understanding of numerical accuracy and robustness.