CCSS: Collaborative Research: Sketching for High Dimensional Data Analysis in IoT

物联网设备的激增产生了海量的数据，这导致了对传输、处理和存储资源的巨大需求。为了提取有用的信息，充分发挥物联网用于智能决策的潜力，开发新的系统来高效地传输、存储和处理这些海量数据至关重要。幸运的是，物联网和许多其他应用程序生成的数据通常具有某些低维简约结构。利用物联网数据的这些低维结构，该项目将开发基于低维草图的方法来推断感兴趣的信息。这个基于草图的框架将实现快速准确的信息提取，并大大降低采样率、传输和存储成本。本项目将开发一个基于草图的框架，用于高效处理物联网产生的高维数据，并研究其理论和算法特性。其核心思想是对随机变量进行低维投影或勾画，而不是直接全面地观察高维随机变量。该项目将开发非自适应和自适应低维素描方法，并将做出以下智力贡献：1)推导用于恢复高维随机变量统计信息的采样率的基本极限；2)设计达到相应的采样率基本极限的显式采样方案；3)为从随机变量的素描中恢复统计信息提供快速算法的性能保证。私人投资机构将利用他们在压缩传感、低阶矩阵恢复和顺序分析方面的研究经验来解决这些具有挑战性的问题。所产生的结果预计将把压缩传感从绘制确定性值的草图扩展到绘制随机变量的更广泛的背景。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The proliferation of IoT devices generates enormous amount of data, which leads to a tremendous demand on resources for the transmission, processing and storage. In order to extract useful information and fully achieve the potential of IoT for intelligent decisions, it is critical to develop novel systems to efficiently transmit, store and process this large volume of data. Fortunately, the data generated by IoT and many other applications typically possesses certain low dimensional parsimonious structures. Leveraging on these low dimensional structures of IoT data, this project will develop methods based on low dimensional sketches to infer information of interest. This sketching based framework will enable quick and accurate information extraction with greatly reduced sampling rates, transmission and storage costs.This project will develop a sketching based framework for the efficient processing of high dimensional data generated by IoT and investigate its theoretical and algorithmic properties. The core idea is to take low dimensional projections or sketches of random variables, rather than to directly and fully observe high dimensional random variables. This project will develop both non-adaptive and adaptive low dimensional sketching methods, and will make the following intellectual contributions: 1) deriving fundamental limits on sampling rates for recovering statistical information of high dimensional random variables; 2) designing explicit sampling schemes that achieve the corresponding fundamental limits on sampling rates; 3) providing fast algorithms with performance guarantees for recovering statistical information from sketches of random variables. The PIs will leverage their research experience in compressed sensing, low-rank matrix recovery and sequential analysis in solving these challenging problems. The generated results are expected to extend compressed sensing from sketching of deterministic values to a broader context of sketching of random variables.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.