Ms.FPOP: A Fast Exact Segmentation Algorithm with a Multiscale Penalty
提出一种名为Ms.FPOP的精确动态规划算法，用于最小化带有多尺度惩罚的最小二乘准则，能高效检测时间序列中的变点，尤其适用于大规模稀疏变点数据，比现有方法更快且更强大。
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 et al. (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 et al. (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 et al. (2012) applied to the multiscale penalty of Verzelen et al. (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 et al. (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.