Divide and Conquer Dynamic Programming: An Almost Linear Time Change Point Detection Methodology in High Dimensions
分治动态规划：高维变点检测的近线性时间方法AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
本页为预印本版本；arXiv 收录、作者填写的期刊信息以及作者既有发表经历，都不单独证明本篇已接收。作者发表记录按 OpenAlex 身份与完整姓名、本站覆盖期刊 ISSN 及正式卷期核对，只展示已核实例，档案仍可能误合并。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要的核心是高维时间序列变点定位，与结构变化方向直接相关，但未提供宏观经济应用证据。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
分治动态规划：高维变点检测的近线性时间方法
- 研究问题
- 面对包含高维特征的时间序列，如何降低变点定位的计算成本，同时保持一致估计和较高的定位精度？
- 方法与思路
- 作者提出分治动态规划框架，采用适用于多类高维模型的贪心算法，并在均值、Gaussian 图模型和线性回归中分析性能。
- 材料陈述的贡献
- 摘要称三类模型均有非渐近定位误差界，部分情形达到最优速率，并以更低计算成本获得合成与真实资料的实验支持。
- 阅读关注点
- 核对近线性复杂度的计量口径、各模型的信号与间隔条件，以及最优速率成立的具体情形和与现有算法比较的设置。
- 阅读边界
- 这是 arXiv 预印本，同行评审或期刊接收未经核实；摘要未列出理论条件和成本数值，不能将部分情形的最优性推广至所有模型。
原文摘要
We develop a novel, general and computationally efficient framework, called Divide and Conquer Dynamic Programming (DCDP), for localizing change points in time series data with high-dimensional features. DCDP deploys a class of greedy algorithms that are applicable to a broad variety of high-dimensional statistical models and can enjoy almost linear computational complexity. We investigate the performance of DCDP in three commonly studied change point settings in high dimensions: the mean model, the Gaussian graphical model, and the linear regression model. In all three cases, we derive non-asymptotic bounds for the accuracy of the DCDP change point estimators. We demonstrate that the DCDP procedures consistently estimate the change points with sharp, and in some cases, optimal rates while incurring significantly smaller computational costs than the best available algorithms. Our findings are supported by extensive numerical experiments on both synthetic and real data.