Kes Ward: Constructing A Constant-per-Iteration Likelihood Ratio Test for Online Changepoint Detection

Online changepoint detection algorithms based on likelihood-ratio tests have excellent statistical properties. However, a simple exact online implementation is computationally infeasible as, at time T, it involves considering O(T) possible locations for the change. To improve on this, we use functional pruning ideas to reduce the set of changepoint locations that need to be stored at time T to approximately log T. Furthermore, we show how we need only maximise the likelihood-ratio test statistic over a small subset of these possible locations. Empirical results show that the resulting exact online algorithm, which can detect changes under a wide range of models, has a constant-per-iteration cost on average. We consider applications of this algorithm in the context of detecting increases in radiation count that represent astronomical or nuclear events of interest.