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.