Home > Research > Publications & Outputs > Online Multivariate Changepoint Detection

Electronic data

  • 2311.01174v1

    Submitted manuscript, 30.9 MB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Keywords

View graph of relations

Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry

Research output: Working paperPreprint

Published
Publication date2/11/2023
PublisherArxiv
<mark>Original language</mark>English

Abstract

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: $\mathcal{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$.

Bibliographic note

31 pages,15 figures