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

我们观察来自分布式和不同高分辨率传感器的大量测量数据的能力急剧增加，这有助于增强我们对许多物理现象的理解。信号处理一直是了解从观测到的测量中看不到的知识的主要驱动力。然而，在过去的十年里，观测的指数增长速度已经超过了我们处理、理解和组织这些海量但有用的信息的计算能力。在这个项目中，研究人员计划将高效的散列算法与随机化数值线性代数相结合，以克服这些计算障碍。该项目将吸引UCB和莱斯大学计算机科学、统计学、欧洲经委会和应用数学方面的不同研究生和本科生。该项目的努力还将通过与一个人权数据分析小组合作，利用散列算法减少估计战争罪行程度的人力，从而推动数据科学的社会公益。该项目的成果将通过OpenStAX CNX向广大受众提供，它将免费向世界各地的任何人分发课程材料，从而促进围绕该主题的充满活力的社区的发展。该项目将实现两个相辅相成的目标：第一，通过直接针对潜在问题提供的下游终端目标而不是中间矩阵近似目标定制随机化，从而扩展RandNLA的基础；第二，使用从这些下游应用程序获得的统计和优化见解来转换和扩展RandNLA的基础。研究人员将提出并扩展几个基本想法，包括概率散列、草图、流、采样、利用分数和随机预测，以使SP显著节省资源。将提供这些权衡的精确数学量化。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.