Ms.FPOP: An Exact and Fast Segmentation Algorithm With a Multiscale Penalty
Ms.FPOP：采用多尺度惩罚的精确快速分段算法AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
本页为预印本版本；arXiv 收录、作者填写的期刊信息以及作者既有发表经历，都不单独证明本篇已接收。作者发表记录按 OpenAlex 身份与完整姓名、本站覆盖期刊 ISSN 及正式卷期核对，只展示已核实例，档案仍可能误合并。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要明确处理时间序列分段常数均值及变点检测与定位，因此归入时间序列和结构变化，未提供特定宏观应用。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
Ms.FPOP：采用多尺度惩罚的精确快速分段算法
- 研究问题
- 对均值分段常数且噪声独立的时间序列，如何精确最小化带多尺度惩罚的最小二乘准则，并提高长序列变点分段效率？
- 方法与思路
- 作者将函数剪枝思想扩展至多尺度惩罚，构建精确动态规划算法 Ms.FPOP，并提供通过 R 调用的高效 C++ 实现。
- 材料陈述的贡献
- 摘要称长序列且真实变点较少时算法通常近似线性并快于 PELT；模拟中，多尺度惩罚方案通常比 BIC 方案更有检验力。
- 阅读关注点
- 应核对精确优化的目标与剪枝依据、复杂度结论的性质、运行时间比较环境，以及惩罚已有理论与新算法贡献的区别。
- 阅读边界
- 所给来源为 arXiv 预印本，不能据此认定已同行评审或期刊接收；速度和检验力结论依赖所述设置，摘要未覆盖相关噪声情形。
原文摘要
Given a time series in $R^n$ 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 \geq 10^5$, 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^6$ in a matter of seconds. Finally, we illustrate on simple simulations that for large enough profiles ($n \geq 10^4$) 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).