DMS-EPSRC: Certifying Accuracy of Randomized Algorithms in Numerical Linear Algebra

在过去的二十年里，最激动人心的发展之一是随机数值线性代数(RNLA)的快速发展。这导致了计算科学的范式转变，使矩阵计算成为史无前例的规模。除了速度之外，RNLA还经常提供具有非凡精确度和健壮性的解决方案。RNLA中的成功案例包括低阶近似、最小二乘问题和迹估计。此外，该领域还见证了在线性系统、特征值问题和张量近似方面的最新进展。尽管有这些成功的故事，但理论和实践之间往往存在着巨大的差距。为了说明这一点，我们来看看“子空间素描”这一任务，这是RNLA的一个关键思想。如果将O(Dlogd)样本用于d维子空间，则有理论支持基于FFT的结构化嵌入(也称为“快速Johnson-Lindenstrauss变换”)提供了保持几何的子空间嵌入。然而，这通常是一个悲观的估计，O(D)，比方说2维样本，已知在实践中出现的大多数问题中都足够了。类似的故事也适用于稀疏的素描，对于稀疏的素描，有美丽的理论可用，但在实践中，它们对特定实例的表现往往要好得多。即使对于确定性算法也是如此，例如列旋转的QR因式分解，特别是它是否给出了揭示等级的QR因式分解。虽然最坏的情况分析表明，该算法可能在指数级上不稳定，但数十年的实际计算表明，这样的例子非常罕见。显然，在这些问题中，有一种方法来评估为手头的特定问题计算的解的正确性将是非常有用的。该建议的目的是开发技术来计算解决线性代数问题的随机算法的特定实例化所引起的误差的上界。这样的界限将允许用户将随机算法的计算速度与经典确定性方法的可靠性结合起来。它还将帮助用户安全地平衡速度和精度的需求。我们在这里提议遵循的方法在精神上与最新的图灵奖获得者杰克·东加拉最近提出的“负责任的鲁莽”算法的概念非常接近。我们的想法是尝试一种快速但可能不稳定的算法，以获得潜在的解决方案。然后，我们以可靠的方式评估解决方案的质量。具体地说，该建议的目的是为该评估开发快速和健壮的算法，从而证明解决方案的正确性，或者以其他方式输出解决方案可能不准确的警告。我们将设计算法，开发理论，并在为现代计算平台优化的开源软件中实现它们。有限元方法的历史发展将有助于我们的项目的背景。首先进行了先验分析，并证明了对有限元空间设计具有不可估量的指导意义的误差界。然而，这些界限过于悲观，无法有效地评估在任何特定实例化中产生的错误，因为界限必须涵盖最具对抗性的输入。作为回应，随后出现了后验分析，因为它具体适用于手头的问题，并可以通过利用计算后可用的数量，提供准确的估计或误差界限。在这个项目中，我们的目标是在RNLA环境下实现同样的目标。我们将追求的具体方向包括：子空间嵌入、低阶逼近、列旋转QR分解、线性系统、特征值问题和奇异值分解、最小二乘问题，以及有效地构造Krylov子空间。

Among the most exciting developments over the last two decades is the rapid advances in randomized numerical linear algebra (RNLA). This has caused a paradigmatic shift in the computational sciences, and has enabled matrix computations of unprecedented scale. In addition to speed, RNLA often provides solutions with exceptional accuracy and robustness. Success stories in RNLA include low-rank approximation, least-squares problems, and trace estimation. In addition, the field has witnessed recent progress in linear systems, eigenvalue problems, and tensor approximation. Despite these success stories, there is often a wide gap between theory and practice. To illustrate, consider the task of "subspace sketching", which is a key idea in RNLA. There is theory to support a claim that structured embeddings (aka "fast Johnson-Lindenstrauss transforms") based on FFTs provide a geometry preserving subspace embedding if O(dlogd) samples are used for a d-dimensional subspace. However, this is usually a pessimistic estimate, and O(d), say 2d samples, is known to suffice in most problems that arise in practice. A similar story holds for sparse sketches, for which beautiful theory is available, but in practice they often perform much better for a particular instance. The same is true even of deterministic algorithms, such as the column-pivoted QR factorization, specifically whether it gives a rank-revealing QR factorization. While the worst-case analysis suggests the algorithm can be exponentially unstable, decades of practical computation has shown that such examples are vanishingly rare. Clearly, in any of these problems, it would be highly useful to have a methodology to assess the correctness of a solution computed for the particular problem at hand.The objective of this proposal is to develop techniques for computing upper bounds on the error incurred by a particular instantiation of a randomized algorithm for solving a linear algebraic problem. Such bounds would allow users to combine the computational speed of randomized algorithms with the reliability of classical deterministic methods. It would also help users in safely balancing the needs of speed and precision. The approach we propose to follow here is close in spirit to the notion of "responsibly reckless" algorithms, recently coined by Jack Dongarra, the latest Turing Award laureate. The idea is to try a fast, but potentially unstable, algorithm, to obtain a potential solution. Then we assess the quality of the solution in a reliable fashion. Specifically, the purpose of this proposal is to develop fast and robust algorithms for this assessment, thereby certifying the correctness of the solution, or otherwise output a warning that the solution may be inaccurate. We will design algorithms, develop theory, and implement them in open-source software optimised for modern computing platforms.The historical development of finite element methods would help put our project in context. A priori analysis came first, and error bounds that were invaluable in guiding the design of finite element spaces were proven. However, these bounds were too pessimistic to usefully assess the error incurred in any particular instantiation, since the bound had to cover the most adversarial input. A posteriori analysis then emerged in response, as it applies specifically to a problem at hand and can, by drawing on quantities available post-computation, provide accurate estimates or bounds on the error. In this project we aim to achieve the same in the RNLA context.Specific directions we will pursue include: Subspace embedding, low-rank approximation, column-pivoted QR factorization, linear systems, eigenvalue problems and SVD, least-squares problems, and building Krylov subspaces efficiently.