Papers › Ms.FPOP: An Exact and Fast Segmentation Algorithm With a Multiscale Penalty
Ms.FPOP: An Exact and Fast Segmentation Algorithm With a Multiscale Penalty
Arnaud Liehrmann, Guillem Rigaill
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Given a time series in Rⁿ with a piecewise constant mean and independent noises, we propose an exact dynamic programming algorithm to minimize a least square criterion with a multiscale penalty promoting well-spread changepoints. Such a penalty has been proposed in Verzelen et al. (2020), and it achieves optimal rates for changepoint detection and changepoint localization. Our proposed algorithm, named Ms.FPOP, extends functional pruning ideas of Rigaill (2015) and Maidstone et al. (2017) to multiscale penalties. For large signals, n ≥10⁵, with relatively few real changepoints, Ms.FPOP is typically quasi-linear and an order of magnitude faster than PELT. We propose an efficient C++ implementation interfaced with R of Ms.FPOP allowing to segment a profile of up to n = 10⁶ in a matter of seconds. Finally, we illustrate on simple simulations that for large enough profiles (n ≥10⁴) Ms.FPOP using the multiscale penalty of Verzelen et al. (2020) is typically more powerfull than FPOP using the classical BIC penalty of Yao (1989).
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections