数据分段算法：单变量均值变化

乔海兰， 克劳迪娅·基尔希

数据分割，即多变化点分析在时间序列分析和信号处理中的重要性，在自然科学和社会科学、医学、工程和金融等各个领域的应用，得到了相当大的关注。 在本次调查的第一部分，我们回顾了现有的关于规范数据分段问题的文献，旨在检测和本地化单变量时间序列均值中的多个变化点。我们概述了有关其计算复杂性和理论特性的流行方法。特别是，我们的理论讨论侧重于与特定过程可检测到哪些变化点的分离率，以及量化相应变化点估计器精度的定位速率，并区分其推导中是否采用了均匀或多尺度视点。我们进一步强调，后一种观点为研究数据分段算法的优等性提供了最为通用的设置。 可以说，规范分段问题是近几十年来提出新的数据分段算法并研究其效率的最流行的框架。在本次调查的第二部分中，我们强调在更简单、单变量环境中深入了解改变点问题的方法的长处和短处的重要性，作为解决更复杂问题的方法的垫脚石。我们用一系列示例来说明复杂分布变化与均值变化之间的连接。我们还讨论了向高维变化点问题的扩展，其中我们证明了高维性带来的挑战对于处理多个变化点时的挑战是正交的。

Data segmentation algorithms: Univariate mean change and beyond

Haeran Cho, Claudia Kirch

Data segmentation a.k.a. multiple change point analysis has received considerable attention due to its importance in time series analysis and signal processing, with applications in a variety of fields including natural and social sciences, medicine, engineering and finance. In the first part of this survey, we review the existing literature on the canonical data segmentation problem which aims at detecting and localising multiple change points in the mean of univariate time series. We provide an overview of popular methodologies on their computational complexity and theoretical properties. In particular, our theoretical discussion focuses on the separation rate relating to which change points are detectable by a given procedure, and the localisation rate quantifying the precision of corresponding change point estimators, and we distinguish between whether a homogeneous or multiscale viewpoint has been adopted in their derivation. We further highlight that the latter viewpoint provides the most general setting for investigating the optimality of data segmentation algorithms. Arguably, the canonical segmentation problem has been the most popular framework to propose new data segmentation algorithms and study their efficiency in the last decades. In the second part of this survey, we motivate the importance of attaining an in-depth understanding of strengths and weaknesses of methodologies for the change point problem in a simpler, univariate setting, as a stepping stone for the development of methodologies for more complex problems. We illustrate this with a range of examples showcasing the connections between complex distributional changes and those in the mean. We also discuss extensions towards high-dimensional change point problems where we demonstrate that the challenges arising from high dimensionality are orthogonal to those in dealing with multiple change points.