RIO-CPD: A Riemannian Geometric Method for Correlation-aware Online Change Point Detection
- URL: http://arxiv.org/abs/2407.09698v2
- Date: Mon, 28 Oct 2024 15:27:01 GMT
- Title: RIO-CPD: A Riemannian Geometric Method for Correlation-aware Online Change Point Detection
- Authors: Chengyuan Deng, Zhengzhang Chen, Xujiang Zhao, Haoyu Wang, Junxiang Wang, Haifeng Chen, Jie Gao,
- Abstract summary: We introduce Rio-CPD, a non-parametric, correlation-aware online change point detection framework.
Rio-CPD employs a novel CUSUM design by computing the geodesic distance between current observations and the Fr'echet mean of prior observations.
We show that Rio-CPD outperforms existing methods on detection accuracy, average detection delay and efficiency.
- Score: 35.945721128755544
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Change point detection aims to identify abrupt shifts occurring at multiple points within a data sequence. This task becomes particularly challenging in the online setting, where different types of changes can occur, including shifts in both the marginal and joint distributions of the data. In this paper, we address these challenges by tracking the Riemannian geometry of correlation matrices, allowing Riemannian metrics to compute the geodesic distance as an accurate measure of correlation dynamics. We introduce Rio-CPD, a non-parametric, correlation-aware online change point detection framework that integrates the Riemannian geometry of the manifold of symmetric positive definite matrices with the cumulative sum (CUSUM) statistic for detecting change points. Rio-CPD employs a novel CUSUM design by computing the geodesic distance between current observations and the Fr\'echet mean of prior observations. With appropriate choices of Riemannian metrics, Rio-CPD offers a simple yet effective and computationally efficient algorithm. Experimental results on both synthetic and real-world datasets demonstrate that Rio-CPD outperforms existing methods on detection accuracy, average detection delay and efficiency.
Related papers
- SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid Registration [76.40993825836222]
We propose SPARE, a novel formulation that utilizes a symmetrized point-to-plane distance for robust non-rigid registration.
The proposed method greatly improves the accuracy of non-rigid registration problems and maintains relatively high solution efficiency.
arXiv Detail & Related papers (2024-05-30T15:55:04Z) - Weakly supervised covariance matrices alignment through Stiefel matrices
estimation for MEG applications [64.20396555814513]
This paper introduces a novel domain adaptation technique for time series data, called Mixing model Stiefel Adaptation (MSA)
We exploit abundant unlabeled data in the target domain to ensure effective prediction by establishing pairwise correspondence with equivalent signal variances between domains.
MSA outperforms recent methods in brain-age regression with task variations using magnetoencephalography (MEG) signals from the Cam-CAN dataset.
arXiv Detail & Related papers (2024-01-24T19:04:49Z) - Learning Radio Environments by Differentiable Ray Tracing [56.40113938833999]
We introduce a novel gradient-based calibration method, complemented by differentiable parametrizations of material properties, scattering and antenna patterns.
We have validated our method using both synthetic data and real-world indoor channel measurements, employing a distributed multiple-input multiple-output (MIMO) channel sounder.
arXiv Detail & Related papers (2023-11-30T13:50:21Z) - Greedy online change point detection [0.0]
Greedy Online Change Point Detection (GOCPD) is a computationally appealing method which finds change points by maximizing the probability of the data coming from the (temporal) concatenation of two independent models.
We show that, for time series with a single change point, this objective is unimodal and thus CPD can be accelerated via ternary search with logarithmic complexity.
arXiv Detail & Related papers (2023-08-14T08:59:59Z) - A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based
on Functional Pruning [5.202524136984542]
We build a flexible nonparametric approach to detect a change in the distribution of a sequence.
Thanks to functional pruning ideas, NP-FOCuS has a computational cost that is log-linear in the number of observations.
In terms of detection power, NP-FOCuS is seen to outperform current nonparametric online changepoint techniques in a variety of settings.
arXiv Detail & Related papers (2023-02-06T11:50:02Z) - A Contrastive Approach to Online Change Point Detection [4.762323642506733]
We suggest a novel procedure for online change point detection.
Our approach expands an idea of maximizing a discrepancy measure between points from pre-change and post-change distributions.
We prove non-asymptotic bounds on the average running length of the procedure and its expected detection delay.
arXiv Detail & Related papers (2022-06-21T07:01:36Z) - Geometric variational inference [0.0]
Variational Inference (VI) or Markov-Chain Monte-Carlo (MCMC) techniques are used to go beyond point estimates.
This work proposes geometric Variational Inference (geoVI), a method based on Riemannian geometry and the Fisher information metric.
The distribution, expressed in the coordinate system induced by the transformation, takes a particularly simple form that allows for an accurate variational approximation.
arXiv Detail & Related papers (2021-05-21T17:18:50Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
inductive biases are central in preventing overfitting empirically.
This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression.
We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
arXiv Detail & Related papers (2021-03-23T17:15:53Z) - Riemannian geometry for Compound Gaussian distributions: application to
recursive change detection [11.90288071168733]
The Fisher information metric is obtained, along with corresponding geodesics and distance function.
This new geometry is applied on a change detection problem on Multivariate Image Times Series.
As shown on simulated data, it allows to reach optimal performance while being computationally more efficient.
arXiv Detail & Related papers (2020-05-20T14:51:09Z) - Assignment Flows for Data Labeling on Graphs: Convergence and Stability [69.68068088508505]
This paper establishes conditions on the weight parameters that guarantee convergence of the continuous-time assignment flow to integral assignments (labelings)
Several counter-examples illustrate that violating the conditions may entail unfavorable behavior of the assignment flow regarding contextual data classification.
arXiv Detail & Related papers (2020-02-26T15:45:38Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.