Publication:106351

DOI10.48550/ARXIV.1004.0887zbMath1381.90094arXiv1004.0887MaRDI QIDQ106351

Guillem Rigaill, Guillem Rigaill

Publication date: 6 April 2010

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: $mathcal{O}(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.

Full work available at URL: https://arxiv.org/abs/1004.0887

zbMATH Keywords

dynamic programmingsegment neighbourhoodfunctional costmultiple-change-point detection

Mathematics Subject Classification ID

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

Related Items (21)

On optimal segmentation and parameter tuning for multiple change-point detection and inference ⋮ Change-point estimation in the multivariate model taking into account the dependence: application to the vegetative development of oilseed rape ⋮ Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection ⋮ Rank-based multiple change-point detection ⋮ Unnamed Item ⋮ Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set ⋮ Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features ⋮ Generalized multiple change-point detection in the structure of multivariate, possibly high-dimensional, data sequences ⋮ Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise ⋮ Cross-validation for change-point regression: pitfalls and solutions ⋮ Tail-greedy bottom-up data decompositions and fast multiple change-point detection ⋮ fpopw ⋮ Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces? ⋮ Relating and comparing methods for detecting changes in mean ⋮ New efficient algorithms for multiple change-point detection with reproducing kernels ⋮ 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 Changes in Slope With an L₀ Penalty ⋮ Changepoint Detection in the Presence of Outliers ⋮ Detecting multiple generalized change-points by isolating single ones

This page was built for publication: A pruned dynamic programming algorithm to recover the best segmentations with $1$ to $K_{max}$ change-points