CAREER: Fast Linear Algebra: Algorithms and Fundamental Limits

计算线性代数是研究解决涉及矩阵和其他线性代数对象的数学问题的算法。它是算法研究中最古老、最实用的子领域之一。线性代数例程是许多大规模科学和工程模拟、信号处理方法、统计和机器学习算法等的核心。最近，通过对算法的研究，该领域发生了革命性的变化，这种算法在执行过程中做出精心选择的随机选择，使得超大规模问题的近似解可以更快地得到解决。这个项目的目的是在这些随机方法的成功基础上，扩大它们的影响范围。这项工作还将确定更快算法的潜力和当今最流行的技术的基本限制。除了在上述应用领域的影响外，该项目还将深化计算线性代数的理论基础，并加强与理论计算机科学、逼近理论、优化、机器学习等领域的联系。这项工作本质上是跨学科的，并将与课程开发相辅相成，重点是让学生准备好跨学科的数学和计算工具包。该项目分为三个主要方面。第一个将考虑基本线性代数问题的计算复杂性，这一点还没有得到很好的理解。在这个过程中，这项工作将探索随机化和近似在快速线性代数中的作用，并赋予该领域缺失的复杂性理论结构来指导算法进步。第二个重点将集中在线性代数计算的受限矩阵-向量查询模型中的算法和下界。这个模型包含了一大部分已知的方法，该项目的目的是解释它在实践中的主导地位，并开发新的算法工具。最后，第三个重点将集中于将随机化方法应用于机器学习、信号处理等领域中出现的结构化矩阵问题。随机化方法在一般非结构化矩阵的计算方面取得了突破，但其在解决结构化问题方面的潜力还未得到充分开发。该项目将解决这一差距，扩大随机方法的实际影响，并加强与计算机科学和应用数学不同领域的理论联系。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Computational Linear Algebra is the study of algorithms for solving mathematical problems involving matrices and other linear-algebraic objects. It is one of the oldest and most practically applicable subfields of algorithms research. Linear-algebraic routines lie at the core of many large-scale scientific and engineering simulations, signal-processing methods, statistical- and machine-learning algorithms, and beyond. Recently, the field has been revolutionized by work on algorithms that make carefully chosen random choices during the course of their execution, allowing much faster approximate solutions for very large-scale problems. This project aims to build on the success of these randomized methods and extend their reach. The work will also identify fundamental limits on the potential for faster algorithms and on today's most popular techniques. Beyond impact in the above mentioned application areas, the project will deepen the theoretical foundations of computational linear algebra and strengthen ties to theoretical computer science, approximation theory, optimization, machine learning, and other fields. The work is interdisciplinary in nature, and will be complemented with curriculum development focused on preparing students with an interdisciplinary mathematical and computing toolkit.The project breaks down into three main thrusts. The first will consider the computational complexity of fundamental linear-algebraic problems, which is not well understood. In the process, the work will explore the role of randomization and approximation in fast linear algebra and endow the field with missing complexity-theoretic structure to guide algorithmic progress. The second thrust will focus on algorithms and lower bounds within the restricted matrix-vector query model of linear-algebraic computation. This model encompasses a large fraction of known approaches, and the project aims to both explain its dominance in practice, and to develop new algorithmic tools. Finally, the third thrust will focus on applying randomized methods to structured matrix problems arising in machine learning, signal processing, and beyond. Randomized methods have led to breakthroughs for computation on general unstructured matrices, but their potential in solving structured problems is under-explored. The project will address this gap, broadening the practical impact of randomized methods, and strengthening theoretical connections to diverse areas of computer science and applied mathematics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.