High-Dimensional Change Point Detection using Graph Spanning Ratio
This provides a versatile solution for timely change detection in high-dimensional data, which is critical for applications like online monitoring, but it is incremental as it builds on graph-based methodologies.
The paper tackles the problem of detecting change points in high-dimensional data by introducing a graph-spanning algorithm that works for both offline and online settings with unknown distributions. It achieves high detection power when changes exceed a minimax separation rate of √(nd), outperforming other methods in accuracy for Gaussian and non-Gaussian data, especially with small observation windows.
Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data across low to high dimensions. This versatile approach is applicable to Euclidean and graph-structured data with unknown distributions, while maintaining control over error probabilities. Theoretically, we demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate, which scales on the order of $\sqrt{nd}$. Our method outperforms other techniques in terms of accuracy for both Gaussian and non-Gaussian data. Notably, it maintains strong detection power even with small observation windows, making it particularly effective for online environments where timely and precise change detection is critical.