Non-parametric Online Change Point Detection on Riemannian Manifolds

Xiuheng Wang, Ricardo Augusto Borsoi, Cédric Richard
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:50143-50162, 2024.

Abstract

Non-parametric detection of change points in streaming time series data that belong to Euclidean spaces has been extensively studied in the literature. Nevertheless, when the data belongs to a Riemannian manifold, existing approaches are no longer applicable as they fail to account for the structure and geometry of the manifold. In this paper, we introduce a non-parametric algorithm for online change point detection in manifold-valued data streams. This algorithm monitors the generalized Karcher mean of the data, computed using stochastic Riemannian optimization. We provide theoretical bounds on the detection and false alarm rate performances of the algorithm, using a new result on the non-asymptotic convergence of the stochastic Riemannian gradient descent. We apply our algorithm to two different Riemannian manifolds. Experimental results with both synthetic and real data illustrate the performance of the proposed method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-wang24f, title = {Non-parametric Online Change Point Detection on {R}iemannian Manifolds}, author = {Wang, Xiuheng and Borsoi, Ricardo Augusto and Richard, C\'{e}dric}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {50143--50162}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/wang24f/wang24f.pdf}, url = {https://proceedings.mlr.press/v235/wang24f.html}, abstract = {Non-parametric detection of change points in streaming time series data that belong to Euclidean spaces has been extensively studied in the literature. Nevertheless, when the data belongs to a Riemannian manifold, existing approaches are no longer applicable as they fail to account for the structure and geometry of the manifold. In this paper, we introduce a non-parametric algorithm for online change point detection in manifold-valued data streams. This algorithm monitors the generalized Karcher mean of the data, computed using stochastic Riemannian optimization. We provide theoretical bounds on the detection and false alarm rate performances of the algorithm, using a new result on the non-asymptotic convergence of the stochastic Riemannian gradient descent. We apply our algorithm to two different Riemannian manifolds. Experimental results with both synthetic and real data illustrate the performance of the proposed method.} }
Endnote
%0 Conference Paper %T Non-parametric Online Change Point Detection on Riemannian Manifolds %A Xiuheng Wang %A Ricardo Augusto Borsoi %A Cédric Richard %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-wang24f %I PMLR %P 50143--50162 %U https://proceedings.mlr.press/v235/wang24f.html %V 235 %X Non-parametric detection of change points in streaming time series data that belong to Euclidean spaces has been extensively studied in the literature. Nevertheless, when the data belongs to a Riemannian manifold, existing approaches are no longer applicable as they fail to account for the structure and geometry of the manifold. In this paper, we introduce a non-parametric algorithm for online change point detection in manifold-valued data streams. This algorithm monitors the generalized Karcher mean of the data, computed using stochastic Riemannian optimization. We provide theoretical bounds on the detection and false alarm rate performances of the algorithm, using a new result on the non-asymptotic convergence of the stochastic Riemannian gradient descent. We apply our algorithm to two different Riemannian manifolds. Experimental results with both synthetic and real data illustrate the performance of the proposed method.
APA
Wang, X., Borsoi, R.A. & Richard, C.. (2024). Non-parametric Online Change Point Detection on Riemannian Manifolds. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:50143-50162 Available from https://proceedings.mlr.press/v235/wang24f.html.

Related Material