Online Change Points Detection for Linear Dynamical Systems with Finite Sample Guarantees
This work addresses the need for reliable change point detection in correlated time series with theoretical guarantees, offering practical guidance for applications like monitoring and control systems, though it is incremental by extending existing methods to more complex scenarios.
The authors tackled the problem of online change point detection in linear dynamical systems with temporal correlations and multiple change points, developing a method with a data-dependent threshold to control false alarm probability and providing finite-sample bounds for detection probability and delay.
The problem of online change point detection is to detect abrupt changes in properties of time series, ideally as soon as possible after those changes occur. Existing work on online change point detection either assumes i.i.d data, focuses on asymptotic analysis, does not present theoretical guarantees on the trade-off between detection accuracy and detection delay, or is only suitable for detecting single change points. In this work, we study the online change point detection problem for linear dynamical systems with unknown dynamics, where the data exhibits temporal correlations and the system could have multiple change points. We develop a data-dependent threshold that can be used in our test that allows one to achieve a pre-specified upper bound on the probability of making a false alarm. We further provide a finite-sample-based bound for the probability of detecting a change point. Our bound demonstrates how parameters used in our algorithm affect the detection probability and delay, and provides guidance on the minimum required time between changes to guarantee detection.