Optimal detection of changepoints with a linear computational cost
From MaRDI portal
Publication:4904735
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)- Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
- Epidemic changepoint detection in the presence of nuisance changes
- Detecting multiple generalized change-points by isolating single ones
- Bayesian P-splines and advanced computing in R for a changepoint analysis on spatio-temporal point processes
- Quasi-hidden Markov model and its applications in change-point problems
- Robust algorithms for multiphase regression models
- Piecewise approximate Bayesian computation: fast inference for discretely observed Markov models using a factorised posterior distribution
- Covariate-assisted matrix completion with multiple structural breaks
- Multiple change points detection in high-dimensional multivariate regression
- Most recent changepoint detection in censored panel data
- A Unified Framework for Change Point Detection in High-Dimensional Linear Models
- Constrained dynamic programming and supervised penalty learning algorithms for peak detection in genomic data
- A general procedure for change-point detection in multivariate time series
- Weak SINDy for partial differential equations
- On optimal segmentation and parameter tuning for multiple change-point detection and inference
- Subsampling based variable selection for generalized linear models
- Changepoint detection in non-exchangeable data
- Multiple change-point detection: a selective overview
- New efficient algorithms for multiple change-point detection with reproducing kernels
- Group orthogonal greedy algorithm for change-point estimation of multivariate time series
- Change-point detection in multinomial data with a large number of categories
- A kernel multiple change-point algorithm via model selection
- High dimensional change point estimation via sparse projection
- A nonparametric approach for multiple change point analysis of multivariate data
- A wavelet-based approach for detecting changes in second order structure within nonstationary time series
- Autocovariance estimation in regression with a discontinuous signal and \(m\)-dependent errors: a difference-based approach
- Autocovariance estimation in the presence of changepoints
- Nonparametric self-exciting models for computer network traffic
- Multiscale jump testing and estimation under complex temporal dynamics
- A comparison of single and multiple changepoint techniques for time series data
- Malware family discovery using reversible jump MCMC sampling of regimes
- Generalized multiple change-point detection in the structure of multivariate, possibly high-dimensional, data sequences
- Optimal change-point detection and localization
- Fast and accurate detection of changes in data streams
- Bayesian Change Point Detection with Spike-and-Slab Priors
- Change-point analysis of asset price bubbles with power-law hazard function
- BOOTSTRAP INFERENCE FOR MULTIPLE CHANGE-POINTS IN TIME SERIES
- Fused-MCP With Application to Signal Processing
- Multiscale change point inference. With discussion and authors' reply
- Multiple change points detection and clustering in dynamic networks
- Univariate mean change point detection: penalization, CUSUM and optimality
- On-line changepoint detection and parameter estimation with application to genomic data
- Multiple change-points detection by empirical Bayesian information criteria and Gibbs sampling induced stochastic search
- Detecting change points in the stress-strength reliability \(P(X < Y)\)
- Testing for dependence on tree structures
- Bayesian multiple changepoint detection for stochastic models in continuous time
- Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
- Multiscale change-point segmentation: beyond step functions
- A computationally efficient nonparametric approach for changepoint detection
- Wavelet-based estimators for mixture regression
- Constrained energy variation for change point detection
- Change-point analysis for binomial autoregressive model with application to price stability counts
- Detecting Changes in Covariance via Random Matrix Theory
- Adaptive detection of multiple change-points in asset price volatility
- Change point detection for nonparametric regression under strongly mixing process
- Nonparametric maximum likelihood approach to multiple change-point problems
- Sequential changepoint detection in neural networks with checkpoints
- Variable importance assessment in sliced inverse regression for variable selection
- scientific article; zbMATH DE number 7370530 (Why is no real title available?)
- AURORA: A Unified fRamework fOR Anomaly detection on multivariate time series
- Seeded intervals and noise level estimation in change point detection: a discussion of Fryzlewicz (2020)
- Emulating complex dynamical simulators with random Fourier features
- Total generalized variation on a tree
- Multiscale blind source separation
- ClaSP: parameter-free time series segmentation
- Mumford-Shah and Potts regularization for manifold-valued data
- p-Variation of CUSUM process and testing change in the mean
- Change surfaces for expressive multidimensional changepoints and counterfactual prediction
- Greedy Segmentation for a Functional Data Sequence
- Consistency of binary segmentation for multiple change-point estimation with functional data
- Change point analysis on the Corinth Gulf (Greece) seismicity
- Improving detection of changepoints in short and noisy time series with local correlations: connecting the events in pixel neighbourhoods
- Identifying multiple changes for a functional data sequence with application to freeway traffic segmentation
- Cross-validation for change-point regression: pitfalls and solutions
- Multiscale Quantile Segmentation
- A pruned recursive solution to the multiple change point problem
- On the modeling of CO\(_2\) EUA and CER prices of EU-ETS for the 2008--2012 period
- An exact approach to Bayesian sequential change point detection
- Detection of spatiotemporal changepoints: a generalised additive model approach
- Change-point inference in high-dimensional regression models under temporal dependence
- Considering long-memory when testing for changepoints in surface temperature: a classification approach based on the time-varying spectrum
- Detecting changes in mixed-sampling rate data sequences
- Optimal scheduling of slots with season segmentation
- Bayesian multiple change-points detection in a normal model with heterogeneous variances
- A Composite Likelihood-Based Approach for Change-Point Detection in Spatio-Temporal Processes
- Computational Outlier Detection Methods in Sliced Inverse Regression
- 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
- Nearly Optimal Change-Point Detection with an Application to Cybersecurity
- Inference for single and multiple change-points in time series
- An efficient two step algorithm for high dimensional change point regression models without grid search
- Wavelet improvement in turning point detection using a hidden Markov model: from the aspects of cyclical identification and outlier correction
- Streaming changepoint detection for transition matrices
- Change detection using an iterative algorithm with guarantees
- Equivariant variance estimation for multiple change-point model
- Threshold estimation for continuous three‐phase polynomial regression models with constant mean in the middle regime
- Jump-penalized least absolute values estimation of scalar or circle-valued signals
- Efficient sparsity adaptive changepoint estimation
- Parametric methodologies for detecting changes in maximum temperature of Tlaxco, Tlaxcala, México
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)
