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

Research

Associated organisational unit

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 paper › Preprint

Published

Standard

Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry. / Pishchagina, Liudmila; Romano, Gaetano; Fearnhead, Paul et al.
Arxiv, 2023.

Research output: Working paper › Preprint

Harvard

Pishchagina, L, Romano, G, Fearnhead, P, Runge, V & Rigaill, G 2023 'Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry' Arxiv. <https://arxiv.org/abs/2311.01174v1>

APA

Pishchagina, L., Romano, G., Fearnhead, P., Runge, V., & Rigaill, G. (2023). Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry. Arxiv. https://arxiv.org/abs/2311.01174v1

Vancouver

Pishchagina L, Romano G, Fearnhead P, Runge V, Rigaill G. Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry. Arxiv. 2023 Nov 2.

Author

Pishchagina, Liudmila ; Romano, Gaetano ; Fearnhead, Paul et al. / Online Multivariate Changepoint Detection : Leveraging Links With Computational Geometry. Arxiv, 2023.

Bibtex

@techreport{186367ca49284e28a0b372c69fa6f699,
title = "Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry",
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$.",
keywords = "stat.CO",
author = "Liudmila Pishchagina and Gaetano Romano and Paul Fearnhead and Vincent Runge and Guillem Rigaill",
note = "31 pages,15 figures",
year = "2023",
month = nov,
day = "2",
language = "English",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

RIS

TY - UNPB

T1 - Online Multivariate Changepoint Detection

T2 - Leveraging Links With Computational Geometry

AU - Pishchagina, Liudmila

AU - Romano, Gaetano

AU - Fearnhead, Paul

AU - Runge, Vincent

AU - Rigaill, Guillem

N1 - 31 pages,15 figures

PY - 2023/11/2

Y1 - 2023/11/2

N2 - 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$.

AB - 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$.

KW - stat.CO

M3 - Preprint

BT - Online Multivariate Changepoint Detection

PB - Arxiv

ER -