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

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

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.