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

PI建议研究矩阵相乘和超定最小二乘问题的随机化算法的数值精度和稳健性。现有的随机化算法分析大多关注精确算法中的时间和空间的渐近复杂性，而对其在浮点算法中的数值行为知之甚少。PI建议为矩阵乘法和最小二乘问题的随机化算法发展一个数值扰动和稳定性理论。这就需要发明新的方法和概念来捕捉随机化算法的数值行为。在这方面，根本不清楚“数字稳定”是什么意思，更不用说它应该如何定义了。如何区分随机化引起的可变性和有限精度引起的可变性？失效概率、概率选择和抽样数量等参数应该考虑在哪里？提出的回答这些问题的方法包括矩阵摄动分析、概率论和矩阵流形上的方法。大量的数值实验将被用来证实分析。随机化算法的动机是需要流式传输对于传统确定性算法来说太大的海量数据集。随机化算法已经成功地应用于模式识别、社会网络分析、种群遗传学、电路测试和文本分类等应用中。建议的研究将有助于确定随机化算法适用于哪些应用领域，并将产生参数选择的实际界限和建议，以实现用户指定的精度。这项拟议的研究具有很高的相关性，因为在高能物理和天文学等应用中，随机化算法将是亿级计算必不可少的，在这些应用中，预计每天都会有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.