Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry

Music City Center 

The increasing volume of data streams poses significant computational challenges for detecting changepoints online. Likelihood-based methods are effective, but their straightforward implementation becomes impractical online. We develop two online algorithms that exactly calculate the likelihood ratio test for a single changepoint in p-dimensional data streams by leveraging fascinating connections with computational geometry. Our first algorithm is straightforward and empirically quasi-linear. The second is more complex but provably quasi-linear: O (n log (n) p+ 1) for n data points. Through simulations, we illustrate, that they are fast and allow us to process millions of points within a matter of minutes up to p= 5.

This is joint work with Liudmila Pishchagina, Guillem Rigaill, Gaetano Romano and Vincent Runge,

Structural breaks

Anomaly detection

Change points

Time series

Online algorithms

Streaming data