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

我们观察来自分布式和不同的高分辨率传感器的大量测量的能力急剧增加，有助于增强我们对许多物理现象的理解。信号处理一直是主要的驱动力，在这方面的知识看不见的观测测量。然而，在过去的十年中，观测数据的指数级增长已经超过了我们处理、理解和组织这些大量但有用的信息的计算能力。在这个项目中，研究人员计划将有效的哈希算法与随机数值线性代数相结合，这可以克服这些计算障碍。该项目将吸引不同的研究生和本科生在计算机科学，统计学，欧洲经委会和应用数学都在UCB和赖斯。该项目的努力还将用于推动数据科学为社会造福，通过与人权数据分析小组合作，利用哈希算法减少人类在估计战争罪程度方面的努力。该项目的成果将通过OpenStax CNX向广大受众提供，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.