Optimal detection of changepoints with a linear computational cost
From MaRDI portal
Abstract: We consider the problem of detecting multiple changepoints in large data sets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example in genetics as we analyse larger regions of the genome, or in finance as we observe time-series over longer periods. We consider the common approach of detecting changepoints through minimising a cost function over possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalised likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints that has a computational cost which, under mild conditions, is linear in the number of observations. This compares favourably with existing methods for the same problem whose computational cost can be quadratic or even cubic. In simulation studies we show that our new method can be orders of magnitude faster than these alternative exact methods. We also compare with the Binary Segmentation algorithm for identifying changepoints, showing that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data.
Recommendations
Cites work
- A Cluster Analysis Method for Grouping Means in the Analysis of Variance
- A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data
- A new look at the statistical model identification
- Algorithms for the optimal identification of segment neighborhoods
- Change detection in autoregressive time series
- Circular binary segmentation for the analysis of array-based DNA copy number data
- Estimating the dimension of a model
- Estimation of a noisy discrete-time step function: Bayes and empirical Bayes approaches
- Minimal penalties for Gaussian model selection
- Multiple Change-Point Estimation With a Total Variation Penalty
- Multiple changepoint fitting via quasilikelihood, with application to DNA sequence segmentation
- On tests for detecting change in mean
- On the detection of changes in autoregressive time series. I: Asymptotics.
- On the underfitting and overfitting sets of models chosen by order selection criteria.
- Structural Break Estimation for Nonstationary Time Series Models
- The maximum likelihood method for testing changes in the parameters of normal observations
Cited in
(only showing first 100 items - show all)- On optimal multiple changepoint algorithms for large data
- A pruned dynamic programming algorithm to recover the best segmentations with 1 to \(K_{\max}\) change-points
- Nonparametric multiple change-point estimation for analyzing large Hi-C data matrices
- Real Time Anomaly Detection And Categorisation
- Labeled Optimal Partitioning
- High-dimensional changepoint detection via a geometrically inspired mapping
- Ensemble binary segmentation for irregularly spaced data with change-points
- Multiple testing of local extrema for detection of change points
- Exact spike train inference via \(\ell_{0}\) optimization
- FDR-control in multiscale change-point segmentation
- A sequential multiple change-point detection procedure via VIF regression
- Continuous monitoring for changepoints in data streams using adaptive estimation
- Fast estimation of posterior probabilities in change-point analysis through a constrained hidden Markov model
- Multiple change points detection and clustering in dynamic networks
- Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
- A heuristic, iterative algorithm for change-point detection in abrupt change models
- A pruned recursive solution to the multiple change point problem
- Inference for a change-point problem under a generalised Ornstein-Uhlenbeck setting
- Super-exponential growth expectations and the global financial crisis
- An exact approach to Bayesian sequential change point detection
- Long memory and changepoint models: a spectral classification procedure
- Bayesian additive regression trees using Bayesian model averaging
- Multiscale blind source separation
- Multiple change-point detection: a selective overview
- New efficient algorithms for multiple change-point detection with reproducing kernels
- Change-point detection in multinomial data with a large number of categories
- A wavelet-based approach for detecting changes in second order structure within nonstationary time series
- Multiple change-points detection by empirical Bayesian information criteria and Gibbs sampling induced stochastic search
- Robust algorithms for multiphase regression models
- Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
- Tail-greedy bottom-up data decompositions and fast multiple change-point detection
- Most recent changepoint detection in censored panel data
- Optimal scheduling of slots with season segmentation
- Bayesian multiple change-points detection in a normal model with heterogeneous variances
- Streaming changepoint detection for transition matrices
- Minimax rates in sparse, high-dimensional change point detection
- Iterative Potts minimization for the recovery of signals with discontinuities from indirect measurements: the multivariate case
- Consistent multiple changepoint estimation with fused Gaussian graphical models
- Bayesian multiple changepoint detection for stochastic models in continuous time
- Change detection using an iterative algorithm with guarantees
- Detection of multiple change points for linear processes under negatively super-additive dependence
- Detecting multiple generalized change-points by isolating single ones
- Model risk in the over-the-counter market
- Mining events with declassified diplomatic documents
- Consistency of a range of penalised cost approaches for detecting multiple changepoints
- Changepoint detection in non-exchangeable data
- Autocovariance estimation in the presence of changepoints
- Dynamic networks with multi-scale temporal structure
- Constrained energy variation for change point detection
- Sequential changepoint detection in neural networks with checkpoints
- A comparison of single and multiple changepoint techniques for time series data
- Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection
- Seeded intervals and noise level estimation in change point detection: a discussion of Fryzlewicz (2020)
- Weak SINDy for partial differential equations
- Change point analysis on the Corinth Gulf (Greece) seismicity
- Variance change point detection for fractional Brownian motion based on the likelihood ratio test
- Scalable change-point and anomaly detection in cross-correlated data with an application to condition monitoring
- Modelling time-varying first and second-order structure of time series via wavelets and differencing
- Parametric methodologies for detecting changes in maximum temperature of Tlaxco, Tlaxcala, México
- On change-point estimation under Sobolev sparsity
- Univariate mean change point detection: penalization, CUSUM and optimality
- Tagore's song-counts by thematic and non-thematic classification: a statistical case study
- Change point detection for nonparametric regression under strongly mixing process
- AURORA: A Unified fRamework fOR Anomaly detection on multivariate time series
- Consistency of binary segmentation for multiple change-point estimation with functional data
- Wavelet improvement in turning point detection using a hidden Markov model: from the aspects of cyclical identification and outlier correction
- Identifying multiple changes for a functional data sequence with application to freeway traffic segmentation
- A shape-based cutting and clustering algorithm for multiple change-point detection
- Nonparametric self-exciting models for computer network traffic
- Multiple changepoint detection with partial information on changepoint times
- Multiscale change-point segmentation: beyond step functions
- Smoothing for signals with discontinuities using higher order Mumford-Shah models
- Dynamic stochastic block models: parameter estimation and detection of changes in community structure
- Multiple changepoint detection in categorical data streams
- A computationally efficient nonparametric approach for changepoint detection
- Inference for multiple change points in heavy-tailed time series via rank likelihood ratio scan statistics
- Nonparametric maximum likelihood approach to multiple change-point problems
- Non-parametric change-point estimation using string matching algorithms
- Faster maximum feasible subsystem solutions for dense constraint matrices
- Modeling a nonlinear biophysical trend followed by long-memory equilibrium with unknown change point
- Estimation of high-dimensional change-points under a group sparsity structure
- Inference for single and multiple change-points in time series
- Mumford-Shah and Potts regularization for manifold-valued data
- Long signal change-point detection
- Malware family discovery using reversible jump MCMC sampling of regimes
- OPTIMAL CHANGE-POINT DETECTION IN TREND MODELS WITH INTEGRATED MOVING AVERAGE ERRORS
- Nearly Optimal Change-Point Detection with an Application to Cybersecurity
- Non-smooth variational regularization for processing manifold-valued data
- Fused-MCP With Application to Signal Processing
- Detecting Changes in Slope With an L0 Penalty
- Simultaneous Credible Regions for Multiple Changepoint Locations
- Parallelization of a Common Changepoint Detection Method
- Adaptive detection of multiple change-points in asset price volatility
- An algorithmic framework for Mumford-Shah regularization of inverse problems in imaging
- Changepoint estimation: another look at multiple testing problems
- Jump-penalized least absolute values estimation of scalar or circle-valued signals
- High dimensional change point estimation via sparse projection
- On the modeling of CO₂ EUA and CER prices of EU-ETS for the 2008--2012 period
- Wavelet-based estimators for mixture regression
- Wild binary segmentation for multiple change-point detection
This page was built for publication: Optimal detection of changepoints with a linear computational cost
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4904735)
