Detecting Changes in Slope With an L0 Penalty

By Paul Fearnhead, Robert Maidstone, Adam N. Letchford. Journal of Computational And Graphical Statistics, 2017

70 citations recorded by the source corpus.

ABSTRACT While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L0 penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L0 penalty is more reliable at estimating changepoint locations than using an L1 penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online.

Subfields: Artificial Intelligence, Molecular Biology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/cedbc42ccccc2ca55a0f4fa1bc308fecbaa37b0e