CAREER: Frontiers in Matrix Sketching

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

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.