Online multivariate changepoint detection: leveraging links with computational geometry
Liudmila Pishchagina, Gaetano Romano, Paul Fearnhead, Vincent Runge, Guillem Rigaill
Journal of the Royal Statistical Society: Series B (Statistical Methodology) · 2026 · Volume 88 · Issue 1
Abstract
The increasing volume of data streams poses significant computational challenges for detecting changepoints online. Likelihood-based methods are effective, but a naive sequential implementation becomes impractical online due to high computational costs. We develop an online algorithm that exactly calculates the likelihood ratio test for a single changepoint inp-dimensional data streams by leveraging a fascinating connection with computational geometry. This connection straightforwardly allows us to exactly recover sparse likelihood ratio statistics: that is assuming only a subset of the dimensions are changing. Our algorithm is straightforward, fast, and apparently quasi-linear. A dyadic variant of our algorithm is provably quasi-linear, beingO(nlog(n)p+1)forndata points andpless than 3, but slower in practice. These algorithms are computationally impractical whenpis larger than 5, and we provide an approximate algorithm suitable for suchpwhich isO(nplog(n)p~+1),for some user-specifiedp~≤5. We derive statistical guarantees for the proposed procedures in the Gaussian case, and confirm the good computational and statistical performance, and usefulness, of the algorithms on both empirical data and NBA data.
Keywords
computational geometry, convex hull, dynamic programming, online changepoint detection
Enable JavaScript for citation tools and additional paper interactions.