BIGDATA: F: Collaborative Research: Theory and Practice of Randomized Algorithms for Ultra-Large-Scale Signal Processing

BIGDATA：F：协作研究：超大规模信号处理随机算法的理论与实践

• 批准号: 1838131
• 负责人: Michael Mahoney
• 金额: $ 40万
• 依托单位: International Computer Science Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-12-01 至 2022-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1838131&HistoricalAwards=false
• 关键词: BIGDATA; Collaborative; Research; Theory; Practice

The dramatic increases in our abilities to observe massive amounts of measurements coming from distributed and disparate high-resolution sensors have been instrumental in enhancing our understanding of many physical phenomena. Signal processing has been the primary driving force in this knowledge of the unseen from observed measurements. However, in the last decade, the exponential increase in observations has outpaced our computing abilities to process, understand, and organize this massive but useful information. In this project the investigators plan to blend efficient hashing algorithms with Randomized Numerical Linear Algebra, which can overcome these computational barriers. The project will engage diverse graduate and undergraduate students in computer science, statistics, ECE, and applied mathematics both at UCB and Rice. The efforts of this project will also be utilized to push data science for social good, through collaborations with a human rights data analysis group in leveraging hashing algorithms to reduce human efforts in estimating the extent of war crimes. The results of the project will be made available to a wide audience through OpenStax CNX, which will to disseminate course materials free-of-charge to anyone in the world and thereby foster the growth of vibrant communities around the subject.This project will achieve two complementary goals: first, extend the foundations of RandNLA by tailoring randomization directly towards downstream end goals provided by the underlying problem, rather than intermediate matrix approximations goals; and second, use the statistical and optimization insights obtained from these downstream applications to transform and extend the foundations of RandNLA. The investigators will propose and extend several fundamental ideas, including probabilistic hashing, sketching, streaming, sampling, leverage scores, and random projections, to make SP significantly resource-frugal. Precise mathematical quantification of these tradeoffs will be provided.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.

我们观察来自分布式和不同的高分辨率传感器的大量测量的能力的显着提高有助于增强我们对许多物理现象的理解。信号处理一直是通过观察测量了解未知事物的主要驱动力。然而，在过去的十年中，观测数据的指数级增长已经超出了我们处理、理解和组织这些大量但有用的信息的计算能力。在这个项目中，研究人员计划将高效的哈希算法与随机数值线性代数相结合，这可以克服这些计算障碍。该项目将吸引 UCB 和莱斯大学计算机科学、统计学、ECE 和应用数学领域的不同研究生和本科生参与。该项目还将通过与人权数据分析小组合作，利用哈希算法来减少人类估计战争罪行程度的努力，从而推动数据科学造福社会。该项目的成果将通过 OpenStax CNX 向广大受众公开，该项目将向世界上任何人免费传播课程材料，从而促进围绕该主题的充满活力的社区的发展。该项目将实现两个目标补充目标：首先，通过直接针对潜在问题提供的下游最终目标（而不是中间矩阵近似目标）定制随机化来扩展 RandNLA 的基础；其次，利用从这些下游应用程序获得的统计和优化见解来改造和扩展 RandNLA 的基础。研究人员将提出并扩展几个基本想法，包括概率散列、草图、流式传输、采样、杠杆分数和随机预测，以使 SP 显着节约资源。将提供这些权衡的精确数学量化。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。