权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: Frontiers in Matrix Sketching

职业：矩阵草图的前沿

基本信息

批准号：
2045590
负责人：
Christopher Musco
金额：
$ 56.28万
依托单位：
New York University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-04-01 至 2026-03-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2045590&HistoricalAwards=false
关键词：
CAREER Frontiers Matrix Sketching

项目摘要

Advances in sensing and storage technology have increased the ability to collect and share huge amounts of data. From satellite imagery, to genetic data, to web content, richer datasets offer the promise of improved data-driven discovery and decision making across science, engineering, and industry. Realizing this promise, however, requires enormous computational effort. The goal of this project is to democratize the data revolution by developing new algorithms to efficiently process the world's largest datasets, without the need for the world's largest supercomputers. To do so, the investigator and his team will study a powerful algorithmic technique known as "matrix sketching". The key idea is to quickly compress a large dataset (represented as a matrix of numbers) down to its most essential information by eliminating redundancy and noise. The compressed data can then be efficiently digested by downstream algorithms for machine learning and statistical inference. This project will advance the state-of-the-art in matrix sketching by taking an interdisciplinary approach, combining tools from theoretical computer science with methods from computational and applied mathematics. The project also involves a major educational component, aimed at improving U.S. mathematics education through closer ties with applications in STEM fields. The project will support an international high-school applied-mathematics competition, the development of curricular material and workshops for high-school educators, and course development to better prepare university students for careers in algorithms, machine learning, and data science. To advance research in matrix sketching, the project is centered around three main objectives, each involving problems of practical importance, as well as motivating theoretical questions that will more broadly impact algorithms research. The first objective is to develop sketching techniques that move beyond low-rank matrix compression, which only captures information about the largest-magnitude components of a matrix’s spectrum. Motivated by emerging applications in network science, deep learning, and computational physics, the research team is developing techniques that instead capture coarse information about the entire spectrum of a matrix. The second objective is to develop methods that allow for higher accuracy by combining existing sketching algorithms with powerful tools for interactive refinement. The goal is to design algorithms with runtimes that depend logarithmically, instead of polynomially, on problem accuracy. The final objective is to extend the impact of sketching beyond applications where data is over-abundant, by addressing important problems where sufficient, high-quality data remains a luxury. The theoretical tools of matrix sketching and data subsampling are being used to design smarter data-collection strategies for the “small-data” regime, advancing the state-of-the-art in active learning and experimental design.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.

传感和存储技术的进步提高了收集和共享大量数据的能力。从卫星图像到遗传数据，再到网络内容，更丰富的数据集为科学、工程和工业领域改进数据驱动的发现和决策提供了希望。然而，实现这一承诺需要大量的计算工作。该项目的目标是通过开发新的算法来有效地处理世界上最大的数据集，而不需要世界上最大的超级计算机来实现数据革命的民主化。为此，研究人员和他的团队将研究一种强大的算法技术，称为“矩阵素描”。其关键思想是通过消除冗余和噪声来快速压缩大型数据集（表示为数字矩阵），以获得最基本的信息。然后，压缩后的数据可以通过下游机器学习和统计推理算法有效地消化。该项目将通过跨学科的方法，将理论计算机科学的工具与计算和应用数学的方法相结合，推进矩阵草图的最新技术。该项目还涉及一个重要的教育组成部分，旨在通过与STEM领域的应用建立更紧密的联系来改善美国的数学教育。该项目将支持国际高中应用数学竞赛，为高中教育工作者开发课程材料和研讨会，以及课程开发，以更好地为大学生在算法，机器学习和数据科学方面的职业生涯做好准备。为了推进矩阵素描的研究，该项目围绕三个主要目标，每个目标都涉及具有实际重要性的问题，以及激发理论问题，这些问题将更广泛地影响算法研究。第一个目标是开发超越低秩矩阵压缩的草图技术，低秩矩阵压缩仅捕获关于矩阵频谱的最大幅度分量的信息。受网络科学、深度学习和计算物理学中新兴应用的启发，研究团队正在开发一种技术，以捕获关于矩阵整个频谱的粗略信息。第二个目标是开发方法，允许更高的准确性，通过结合现有的草图算法与强大的工具进行交互式细化。我们的目标是设计算法的运行时依赖于数学，而不是多项式，问题的准确性。最终目标是通过解决足够的高质量数据仍然是奢侈品的重要问题，将草图绘制的影响扩展到数据过于丰富的应用程序之外。矩阵草图和数据子采样的理论工具被用于为“小数据”制度设计更智能的数据收集策略，推进主动学习和实验设计的最新技术。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量（22）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Near-Linear Sample Complexity for $L_p$ Polynomial Regression

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

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
R. A. Meyer;Cameron Musco;Christopher Musco;David P. Woodruff;Samson Zhou
通讯作者：
Samson Zhou

Structured Semidefinite Programming for Recovering Structured Preconditioners

用于恢复结构化预条件子的结构化半定规划

DOI：
发表时间：
2023
期刊：
Advances in Neural Information Processing Systems
影响因子：
0
作者：
Jambulapati, Arun;Li, Jerry;Musco, Christopher;Shiragur, Kirankumar;Sidford, Aaron;Tian, Kevin
通讯作者：
Tian, Kevin

Dimensionality Reduction for General {KDE} Mode Finding

一般 {KDE} 模式查找的降维

DOI：
发表时间：
2023
期刊：
Proceedings of the 40th International Conference on Machine Learning
影响因子：
0
作者：
Luo, Xinyu;Musco, Christopher;Widdershoven, Cas
通讯作者：
Widdershoven, Cas

Active Learning for Single Neuron Models with Lipschitz Non-Linearities

具有 Lipschitz 非线性的单神经元模型的主动学习

DOI：
发表时间：
2023
期刊：
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics
影响因子：
0
作者：
Gajjar, Aarshvi;Musco, Christopher;Hegde, Chinmay
通讯作者：
Hegde, Chinmay

Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation

最优有理矩阵函数逼近的低内存 Krylov 子空间方法