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 的法定使命，并通过使用基金会的智力优点和应用程序进行评估，被认为值得支持。更广泛的影响审查标准。

项目成果

Kernel Interpolation with Sparse Grids

稀疏网格的核插值

• 发表时间: 2022-01
• 期刊: Conference on Neural Information Processing Systems (NeurIPS
• 作者: Yadav, Mohit;Sheldon, Daniel;Musco, Cameron
• 通讯作者: Musco, Cameron

Faster Kernel Matrix Algebra via Density Estimation.

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

• 发表时间: 2021-01
• 期刊: International Conference on Machine Learning (ICML
• 作者: Backurs, Arturs;Indyk, Piotr;Musco, Cameron;Wagner, Tal.
• 通讯作者: Wagner, Tal.

Active Linear Regression for Lp Norms and Beyond

Lp 范数及以上的主动线性回归

• DOI: 10.1109/focs54457.2022.00076
• 发表时间: 2022-10
• 期刊: IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022
• 作者: Musco, Cameron;Musco, Christopher;Woodruff, David P.;Yasuda, Taisuke
• 通讯作者: Yasuda, Taisuke

Optimal Sketching Bounds for Sparse Linear Regression

稀疏线性回归的最佳草图边界

• DOI: 10.48550/arxiv.2304.02261
• 发表时间: 2023-04-05
• 作者: Tung Mai;Ale;er Munteanu;er;Cameron Musco;Anup B. Rao;Chris Schwiegelshohn;David P. Woodruff
• 通讯作者: David P. Woodruff

Near-Linear Sample Complexity for Lp Polynomial Regression

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

• 发表时间: 2023-01
• 期刊: ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Meyer, Raphael;Musco, Cameron;Musco, Christopher;Woodruff, David P.;Zhou, Samson
• 通讯作者: Zhou, Samson