Online Change Points Detection for Linear Dynamical Systems with Finite
  Sample Guarantees
Lei Xin George Chiu Shreyas Sundaram
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.