A pruned dynamic programming algorithm to recover the best segmentations with 1 to K_ change-points
From MaRDI portal
Publication:106351
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.
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
Cited in
(26)- Seeded binary segmentation: a general methodology for fast and optimal changepoint detection
- 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
- Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
- Cross-validation for change-point regression: pitfalls and solutions
- A pruned recursive solution to the multiple change point problem
- Detecting Changes in Slope With an L0 Penalty
- fpopw
- Bayesian Hierarchical Model for Change Point Detection in Multivariate Sequences
- Mixture of segmentation for heterogeneous functional data
- On optimal multiple changepoint algorithms for large data
- Multiple change-point detection for regression curves
- Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
- A shape-based cutting and clustering algorithm for multiple change-point detection
- Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features
- Changepoint Detection in the Presence of Outliers
- Rank-based multiple change-point detection
- 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
- 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)
