CAREER: Fast Linear Algebra: Algorithms and Fundamental Limits

职业：快速线性代数：算法和基本限制

• 批准号: 2046235
• 负责人: Cameron Musco
• 金额: $ 57.12万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2046235&HistoricalAwards=false
• 关键词: CAREER; Fast; Linear; Algebra; Algorithms

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.

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

项目成果

Error bounds for Lanczos-based matrix function approximation

• DOI: 10.1137/21m1427784
• 发表时间: 2021-06
• 期刊: ArXiv
• 作者: Tyler Chen;A. Greenbaum;Cameron Musco;Christopher Musco

Faster Kernel Matrix Algebra via Density Estimation

通过密度估计更快的核矩阵代数

• 发表时间: 2021
• 期刊: International Conference on Machine Learning
• 作者: Backurs, A;Indyk, P;Musco, C;Wagner, T
• 通讯作者: Wagner, T

Near-Linear Sample Complexity for $L_p$ Polynomial Regression

$L_p$ 多项式回归的近线性样本复杂度

• 发表时间: 2022
• 作者: R. A. Meyer;Cameron Musco;Christopher Musco;David P. Woodruff;Samson Zhou
• 通讯作者: Samson Zhou

Sample Constrained Treatment Effect Estimation

样本约束处理效果估计

• 发表时间: 2022
• 期刊: Conference on Neural Information Processing Systems (NeurIPS
• 作者: Addanki, Raghavendra;Arbour, David;Mai, Tung;Musco, Cameron;Rao, Anup B.
• 通讯作者: Rao, Anup B.

Kernel Interpolation with Sparse Grids

• DOI: 10.48550/arxiv.2305.14451
• 发表时间: 2023-05
• 期刊: ArXiv
• 作者: Mohit Yadav;D. Sheldon;Cameron Musco