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

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.

31 pages, An extended version of the pre-print

Cited by in corpus (14)

• Selective review of offline change point detection methods
• Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
• Multiple Change Point Analysis: Fast Implementation And Strong Consistency
• Data segmentation algorithms: Univariate mean change and beyond
• A review on minimax rates in change point detection and localisation
• Sequential change point tests based on U-statistics
• Detecting changes in slope with an $L_0$ penalty
• Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
• Geometric-Based Pruning Rules For Change Point Detection in Multiple Independent Time Series
• Online detection of cascading change-points
• New efficient algorithms for multiple change-point detection with kernels
• Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry
• A new segmentation method for the homogenisation of GNSS-derived IWV time-series
• Change-in-Slope Optimal Partitioning Algorithm in a Finite-Size Parameter Space