Optimal detection of changepoints with a linear computational cost
From MaRDI portal
Publication:4904735
DOI10.1080/01621459.2012.737745zbMATH Open1258.62091arXiv1101.1438OpenAlexW1975684011WikidataQ105583949 ScholiaQ105583949MaRDI QIDQ4904735FDOQ4904735
Authors: Rebecca Killick, Paul Fearnhead, Idris A. Eckley 
Publication date: 31 January 2013
Published in: Journal of the American Statistical Association (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1101.1438
Recommendations
Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Parametric inference (62F99) Dynamic programming (90C39)
Cites Work
- Estimating the dimension of a model
- A new look at the statistical model identification
- A Cluster Analysis Method for Grouping Means in the Analysis of Variance
- Algorithms for the optimal identification of segment neighborhoods
- Multiple changepoint fitting via quasilikelihood, with application to DNA sequence segmentation
- Multiple Change-Point Estimation With a Total Variation Penalty
- Circular binary segmentation for the analysis of array-based DNA copy number data
- A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data
- Structural Break Estimation for Nonstationary Time Series Models
- The maximum likelihood method for testing changes in the parameters of normal observations
- Minimal penalties for Gaussian model selection
- On tests for detecting change in mean
- Change detection in autoregressive time series
- Estimation of a noisy discrete-time step function: Bayes and empirical Bayes approaches
- On the detection of changes in autoregressive time series. I: Asymptotics.
- On the underfitting and overfitting sets of models chosen by order selection criteria.
Cited In (only showing first 100 items - show all)
- Detecting multiple generalized change-points by isolating single ones
- A general procedure for change-point detection in multivariate time series
- Constrained dynamic programming and supervised penalty learning algorithms for peak detection in genomic data
- On optimal segmentation and parameter tuning for multiple change-point detection and inference
- Most recent changepoint detection in censored panel data
- 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
- Group orthogonal greedy algorithm for change-point estimation of multivariate time series
- Autocovariance estimation in regression with a discontinuous signal and \(m\)-dependent errors: a difference-based approach
- A nonparametric approach for multiple change point analysis of multivariate data
- High dimensional change point estimation via sparse projection
- A kernel multiple change-point algorithm via model selection
- A wavelet-based approach for detecting changes in second order structure within nonstationary time series
- Univariate mean change point detection: penalization, CUSUM and optimality
- Multiple change-points detection by empirical Bayesian information criteria and Gibbs sampling induced stochastic search
- On-line changepoint detection and parameter estimation with application to genomic data
- Bayesian multiple changepoint detection for stochastic models in continuous time
- Multiscale change-point segmentation: beyond step functions
- Wavelet-based estimators for mixture regression
- A computationally efficient nonparametric approach for changepoint detection
- Adaptive detection of multiple change-points in asset price volatility
- Nonparametric maximum likelihood approach to multiple change-point problems
- Mumford-Shah and Potts regularization for manifold-valued data
- Dynamic stochastic block models: parameter estimation and detection of changes in community structure
- Detecting Changes in Slope With an L0 Penalty
- Changepoint estimation: another look at multiple testing problems
- Inference for single and multiple change-points in time series
- Change detection using an iterative algorithm with guarantees
- Change-Point Detection for Graphical Models in the Presence of Missing Values
- Nonparametric product partition models for multiple change-points analysis
- Product partition latent variable model for multiple change-point detection in multivariate data
- An \(L_0\)-norm regularized method for multivariate time series segmentation
- A sequential multiple change-point detection procedure via VIF regression
- Continuous monitoring for changepoints in data streams using adaptive estimation
- Ensemble binary segmentation for irregularly spaced data with change-points
- Exact spike train inference via \(\ell_{0}\) optimization
- Detecting non-simultaneous changes in means of vectors
- Wild binary segmentation for multiple change-point detection
- High-dimensional changepoint detection via a geometrically inspired mapping
- Multiple testing of local extrema for detection of change points
- On optimal multiple changepoint algorithms for large data
- Two-stage data segmentation permitting multiscale change points, heavy tails and dependence
- An algorithmic framework for Mumford-Shah regularization of inverse problems in imaging
- Inference of Breakpoints in High-dimensional Time Series
- Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features
- Multiscale Change Point Inference
- Detecting Abrupt Changes in High-Dimensional Self-Exciting Poisson Processes
- Localising change points in piecewise polynomials of general degrees
- Optimal nonparametric change point analysis
- Optimal covariance change point localization in high dimensions
- FDR-control in multiscale change-point segmentation
- Consistent selection of the number of change-points via sample-splitting
- Changepoint Detection in the Presence of Outliers
- Long signal change-point detection
- Rank-based multiple change-point detection
- Multiple change-points detection in high dimension
- Subset Multivariate Collective and Point Anomaly Detection
- 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
- Graphical Influence Diagnostics for Changepoint Models
- Identifying multiple changepoints in heterogeneous binary data with an application to molecular genetics
- Labeled Optimal Partitioning
- Data-driven selection of the number of change-points via error rate control
- Fast estimation of posterior probabilities in change-point analysis through a constrained hidden Markov model
- Bayesian additive regression trees using Bayesian model averaging
- Detecting Multiple Change Points: The PULSE Criterion
- Dynamic networks with multi-scale temporal structure
- A heuristic, iterative algorithm for change-point detection in abrupt change models
- Tail-greedy bottom-up data decompositions and fast multiple change-point detection
- Piecewise approximate Bayesian computation: fast inference for discretely observed Markov models using a factorised posterior distribution
- A Unified Framework for Change Point Detection in High-Dimensional Linear Models
- Robust algorithms for multiphase regression models
- Weak SINDy for partial differential equations
- Changepoint detection in non-exchangeable data
- Autocovariance estimation in the presence of changepoints
- Nonparametric self-exciting models for computer network traffic
- A comparison of single and multiple changepoint techniques for time series data
- Multiple change points detection and clustering in dynamic networks
- Testing for dependence on tree structures
- Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
- Constrained energy variation for change point detection
- Change point detection for nonparametric regression under strongly mixing process
- Variable importance assessment in sliced inverse regression for variable selection
- Sequential changepoint detection in neural networks with checkpoints
- Seeded intervals and noise level estimation in change point detection: a discussion of Fryzlewicz (2020)
- Multiscale blind source separation
- Change point analysis on the Corinth Gulf (Greece) seismicity
- On the modeling of CO\(_2\) EUA and CER prices of EU-ETS for the 2008--2012 period
- A pruned recursive solution to the multiple change point problem
- Computational Outlier Detection Methods in Sliced Inverse Regression
- An exact approach to Bayesian sequential change point detection
- Optimal scheduling of slots with season segmentation
- Bayesian multiple change-points detection in a normal model with heterogeneous variances
- Nearly Optimal Change-Point Detection with an Application to Cybersecurity
- An efficient two step algorithm for high dimensional change point regression models without grid search
- Streaming changepoint detection for transition matrices
- Parametric methodologies for detecting changes in maximum temperature of Tlaxco, Tlaxcala, México
- Scalable change-point and anomaly detection in cross-correlated data with an application to condition monitoring
Uses Software
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)
