A pruned dynamic programming algorithm to recover the best segmentations with 1 to K_ change-points

DOI10.48550/ARXIV.1004.0887MaRDI QIDQ106351zbMATH OpenFDO

Authors Guillem Rigaill

Publication date 6 April 2010

Published in Journal de la Société Française de Statistique (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.0887, http://journal-sfds.fr/article/view/485/

zbMATH Keywords

dynamic programmingfunctional costmultiple-change-point detectionsegment neighbourhood

Mathematics Subject Classification ID

Point estimation (62F10) Linear regression; mixed models (62J05) Inference from stochastic processes (62M99) Dynamic programming (90C39)

Abstract: A common computational problem in multiple change-point models is to recover the segmentations with $1$ to $K_{max}$ 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: $mathcalO(K_{max}{n}^2)$. 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

(34)

• fpopw
• On optimal multiple changepoint algorithms for large data
• Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape
• A pruned recursive solution to the multiple change point problem
• New efficient algorithms for multiple change-point detection with reproducing kernels
• Tail-greedy bottom-up data decompositions and fast multiple change-point detection
• Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
• Detecting multiple generalized change-points by isolating single ones
• Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection
• A shape-based cutting and clustering algorithm for multiple change-point detection
• A computationally efficient nonparametric approach for changepoint detection
• Detecting Changes in Slope With an L₀ Penalty
• Constrained dynamic programming and supervised penalty learning algorithms for peak detection in genomic data
• Rank-based multiple change-point detection
• Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set
• Changepoint Detection in the Presence of Outliers
• Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features
• Seeded binary segmentation: a general methodology for fast and optimal changepoint detection
• On optimal segmentation and parameter tuning for multiple change-point detection and inference
• Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
• Generalized multiple change-point detection in the structure of multivariate, possibly high-dimensional, data sequences
• Relating and comparing methods for detecting changes in mean
• Bayesian Hierarchical Model for Change Point Detection in Multivariate Sequences
• Cross-validation for change-point regression: pitfalls and solutions
• Mixture of segmentation for heterogeneous functional data
• Multiple change-point detection for regression curves
• Online multivariate changepoint detection: leveraging links with computational geometry
• A changepoint approach to modelling nonstationary soil moisture dynamics
• Data-adaptive structural change-point detection via isolation
• Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty
• Efficient Multiple Change Point Detection and Localization For High-Dimensional Quantile Regression with Heteroscedasticity
• An inexact projected regularized Newton method for fused zero-norms regularization problems
• Inference on breaks in weak location time series models with the estimating function approach
• Change Point Detection in Pairwise Comparison Data with Covariates

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)