CIF: Small: Collaborative Research: Sketching and Tracking of Covariance Structures for High-dimensional Streaming Data

CIF：小型：协作研究：高维流数据协方差结构的草图和跟踪

• 批准号: 1422966
• 负责人: Yuejie Chi
• 金额: $ 7.5万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422966&HistoricalAwards=false
• 关键词: CIF; Small; Collaborative; Research; Sketching

The explosion of high-dimensional and high-rate data streams has overwhelmed the computational and storage power of traditional sensor suites, resulting in a severe mismatch between the data generation rate and processing capabilities in modern data-intensive applications: On one hand, vast amounts of data are generated ubiquitously at an unprecedented rate carrying dynamic information that are essential for decision making; on the other hand, limited by processing power and storage capacity, many sensing platforms cannot afford to capture a complete snapshot of the system or store the entire data stream. This research program provides a comprehensive framework for learning and tracking covariance structures of large-scale data streams, which has implications for a broad range of applications in network analysis, active sensing, traffic monitoring, particularly in systems where communication bandwidth, battery life, and physical limits constrain the practicality of high sample rates. By leveraging low-dimensional covariance structures such as sparsity and low-rankness, the research introduces a novel framework for reconstructing and tracking covariance structures of high-dimensional noisy data streams in time-sensitive and resource-constrained environments via low-complexity sketching schemes, showing that a single sketch per sample suffices for accurately reconstructing the covariance matrix rather than the original data stream with minimal storage requirement. The research program develops efficient algorithms with theoretical guarantees as well as investigates the fundamental limits for inferring covariance structures from a limited number of measurements, offering a new combination of insights and techniques from information theory, signal processing and high-dimensional statistics.

高维、高速率数据流的爆炸式增长已经压倒了传统传感器套件的计算和存储能力，导致现代数据密集型应用中数据生成速率与处理能力之间的严重不匹配：一方面，大量数据以前所未有的速率无处不在地生成，携带着决策所必需的动态信息;另一方面，由于处理能力和存储容量的限制，许多传感平台无法捕获系统的完整快照或存储整个数据流。该研究计划提供了一个全面的框架，用于学习和跟踪大规模数据流的协方差结构，这对网络分析，主动传感，流量监控等领域的广泛应用具有影响，特别是在通信带宽，电池寿命和物理限制限制高采样率实用性的系统中。通过利用低维协方差结构，如稀疏性和低秩，该研究引入了一种新的框架，用于通过低复杂度的草图方案在时间敏感和资源受限的环境中重建和跟踪高维噪声数据流的协方差结构，表明每个样本的单个草图足以精确地重建协方差矩阵，而不是以最小的存储来重建原始数据流要求。该研究计划开发具有理论保证的有效算法，并研究从有限数量的测量值推断协方差结构的基本限制，提供信息论，信号处理和高维统计的见解和技术的新组合。