Online Change Points Detection for Linear Dynamical Systems with Finite Sample Guarantees

• URL: http://arxiv.org/abs/2311.18769v1
• Date: Thu, 30 Nov 2023 18:08:16 GMT
• Title: Online Change Points Detection for Linear Dynamical Systems with Finite Sample Guarantees
• Authors: Lei Xin, George Chiu, Shreyas Sundaram
• Abstract summary: We study the online change point detection problem for linear dynamical systems with unknown dynamics. We develop a data-dependent threshold that can be used in our test that allows one to achieve a pre-specified upper bound on the probability of making a false alarm.
• Score: 1.6026317505839445
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of online change point detection is to detect abrupt changes in properties of time series, ideally as soon as possible after those changes occur. Existing work on online change point detection either assumes i.i.d data, focuses on asymptotic analysis, does not present theoretical guarantees on the trade-off between detection accuracy and detection delay, or is only suitable for detecting single change points. In this work, we study the online change point detection problem for linear dynamical systems with unknown dynamics, where the data exhibits temporal correlations and the system could have multiple change points. We develop a data-dependent threshold that can be used in our test that allows one to achieve a pre-specified upper bound on the probability of making a false alarm. We further provide a finite-sample-based bound for the probability of detecting a change point. Our bound demonstrates how parameters used in our algorithm affect the detection probability and delay, and provides guidance on the minimum required time between changes to guarantee detection.

Related papers

• 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 Robust and Explainable Data-Driven Anomaly Detection Approach For Power Electronics [56.86150790999639]
  We present two anomaly detection and classification approaches, namely the Matrix Profile algorithm and anomaly transformer. The Matrix Profile algorithm is shown to be well suited as a generalizable approach for detecting real-time anomalies in streaming time-series data. A series of custom filters is created and added to the detector to tune its sensitivity, recall, and detection accuracy.
  arXiv  Detail & Related papers  (2022-09-23T06:09:35Z)
• High dimensional change-point detection: a complete graph approach [0.0]
  We propose a complete graph-based, change-point detection algorithm to detect change of mean and variance from low to high-dimensional online data. Inspired by complete graph structure, we introduce graph-spanning ratios to map high-dimensional data into metrics. Our approach has high detection power with small and multiple scanning window, which allows timely detection of change-point in the online setting.
  arXiv  Detail & Related papers  (2022-03-16T15:59:20Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• WATCH: Wasserstein Change Point Detection for High-Dimensional Time Series Data [4.228718402877829]
  Change point detection methods have the ability to discover changes in an unsupervised fashion. We propose WATCH, a novel Wasserstein distance-based change point detection approach. An extensive evaluation shows that WATCH is capable of accurately identifying change points and outperforming state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-01-18T16:55:29Z)
• Bandit Quickest Changepoint Detection [55.855465482260165]
  Continuous monitoring of every sensor can be expensive due to resource constraints. We derive an information-theoretic lower bound on the detection delay for a general class of finitely parameterized probability distributions. We propose a computationally efficient online sensing scheme, which seamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions.
  arXiv  Detail & Related papers  (2021-07-22T07:25:35Z)
• Online Neural Networks for Change-Point Detection [0.6015898117103069]
  We present two online change-point detection approaches based on neural networks. We compare them with the best known algorithms on various synthetic and real world data sets.
  arXiv  Detail & Related papers  (2020-10-03T16:55:59Z)
• Partially Observable Online Change Detection via Smooth-Sparse Decomposition [16.8028358824706]
  We consider online change detection of high dimensional data streams with sparse changes, where only a subset of data streams can be observed at each sensing time point due to limited sensing capacities. On the one hand, the detection scheme should be able to deal with partially observable data and meanwhile have efficient detection power for sparse changes. In this paper, we propose a novel detection scheme called CDSSD. In particular, it describes the structure of high dimensional data with sparse changes by smooth-sparse decomposition.
  arXiv  Detail & Related papers  (2020-09-22T16:03:04Z)
• Change Point Detection in Time Series Data using Autoencoders with a Time-Invariant Representation [69.34035527763916]
  Change point detection (CPD) aims to locate abrupt property changes in time series data. Recent CPD methods demonstrated the potential of using deep learning techniques, but often lack the ability to identify more subtle changes in the autocorrelation statistics of the signal. We employ an autoencoder-based methodology with a novel loss function, through which the used autoencoders learn a partially time-invariant representation that is tailored for CPD.
  arXiv  Detail & Related papers  (2020-08-21T15:03:21Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)
• Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes [72.68201611113673]
  This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. We assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available.
  arXiv  Detail & Related papers  (2020-03-13T23:39:40Z)

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.