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

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

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.