A pruned dynamic programming algorithm to recover the best segmentations with 1 to K_ change-points
From MaRDI portal
DOI10.48550/ARXIV.1004.0887zbMATH Open1381.90094arXiv1004.0887MaRDI QIDQ106351FDOQ106351
Authors: Guillem Rigaill 
Publication date: 6 April 2010
Published in: Journal de la Société Française de Statistique (Search for Journal in Brave)
Abstract: A common computational problem in multiple change-point models is to recover the segmentations with to change-points of minimal cost with respect to some loss function. Here we present an algorithm to prune the set of candidate change-points which is based on a functional representation of the cost of segmentations. We study the worst case complexity of the algorithm when there is a unidimensional parameter per segment and demonstrate that it is at worst equivalent to the complexity of the segment neighbourhood algorithm: . For a particular loss function we demonstrate that pruning is on average efficient even if there are no change-points in the signal. Finally, we empirically study the performance of the algorithm in the case of the quadratic loss and show that it is faster than the segment neighbourhood algorithm.
Full work available at URL: https://arxiv.org/abs/1004.0887
Recommendations
- On optimal multiple changepoint algorithms for large data
- A pruned recursive solution to the multiple change point problem
- Optimal detection of changepoints with a linear computational cost
- Exploring the latent segmentation space for the assessment of multiple change-point models
- Fitting multiple change-point models to data
Point estimation (62F10) Linear regression; mixed models (62J05) Inference from stochastic processes (62M99) Dynamic programming (90C39)
Cited In (26)
- Detecting multiple generalized change-points by isolating single ones
- 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
- New efficient algorithms for multiple change-point detection with reproducing kernels
- Generalized multiple change-point detection in the structure of multivariate, possibly high-dimensional, data sequences
- Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
- A computationally efficient nonparametric approach for changepoint detection
- Cross-validation for change-point regression: pitfalls and solutions
- Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
- A pruned recursive solution to the multiple change point problem
- Detecting Changes in Slope With an L0 Penalty
- Bayesian Hierarchical Model for Change Point Detection in Multivariate Sequences
- Mixture of segmentation for heterogeneous functional data
- Multiple change-point detection for regression curves
- Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
- On optimal multiple changepoint algorithms for large data
- Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features
- Changepoint Detection in the Presence of Outliers
- A shape-based cutting and clustering algorithm for multiple change-point detection
- Rank-based multiple change-point detection
- fpopw
- Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection
- Relating and comparing methods for detecting changes in mean
- Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set
- Seeded binary segmentation: a general methodology for fast and optimal changepoint detection
- Tail-greedy bottom-up data decompositions and fast multiple change-point detection
This page was built for publication: A pruned dynamic programming algorithm to recover the best segmentations with 1 to \(K_{\max}\) change-points
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q106351)
