Ms.FPOP: a fast exact segmentation algorithm with a multiscale penalty

Given a time series in Rn with a piecewise constant mean and independent noises, we propose an exact dynamic programming algorithm for minimizing a least-squares criterion with a multiscale penalty, favoring well-spread changepoints. This penalty was proposed by Verzelen <i>et al.</i> (2023) and achieves optimal rates for changepoint detection and changepoint localization in a non-asymptotic scenario. Our proposed algorithm, Multiscale Functional Pruning Optimal Partitioning (Ms.FPOP), extends functional pruning ideas presented in Rigaill (2015) and Maidstone <i>et al.</i> (2017) to multiscale penalties. For large signals ( n≥105) with sparse changepoints, Ms.FPOP is shown empirically to be quasi-linear and faster than the Pruned Exact Linear Time (PELT) method of Killick <i>et al.</i> (2012) applied to the multiscale penalty of Verzelen <i>et al.</i> (2023), which exhibits quadratic slowdown in these cases. We propose an efficient implementation of Ms.FPOP coded in C++ interfaced with R that can segment profiles of up to n=106 in a matter of seconds. Our algorithm works for slightly more general multiscale penalties. In particular, it allows a minimum segment length to be imposed. Using simple simulations we then show that where profiles are sufficiently large ( n≥104), Ms.FPOP using the multiscale penalty of Verzelen <i>et al.</i> (2023) is typically more powerful than optimizing a least-squares criterion with the BIC penalty of Yao (1989), a criterion that was shown by Fearnhead and Rigaill 2020 to perfom well across a wide range of scenarios. Supplementary materials for this article are available online.