Data segmentation algorithms: Univariate mean change and beyond

Abstract

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.

References in corpus (34)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Optimal detection of changepoints with a linear computational cost
• Selective review of offline change point detection methods
• An Algorithm for Optimal Partitioning of Data on an Interval
• A tutorial introduction to the minimum description length principle
• Detection of an anomalous cluster in a network
• Properties and refinements of the fused lasso
• Change-point detection in panel data via double CUSUM statistic
• Uniform change point tests in high dimension
• Nonparametric maximum likelihood approach to multiple change-point problems
• The screening and ranking algorithm to detect DNA copy number variations
• Simultaneous multiple change-point and factor analysis for high-dimensional time series
• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• A pruned dynamic programming algorithm to recover the best segmentations with $1$ to $K_{max}$ change-points
• A multiple filter test for the detection of rate changes in renewal processes with varying variance
• Computationally efficient change point detection for high-dimensional regression
• Change-point detection in dynamic networks via graphon estimation
• Statistically and Computationally Efficient Change Point Localization in Regression Settings
• A linear time method for the detection of point and collective anomalies
• Optimal nonparametric change point detection and localization
• Multiscale Change-point Segmentation: Beyond Step Functions
• Multi-sequence segmentation via score and higher-criticism tests
• Studentized U-quantile processes under dependence with applications to change-point analysis
• Intelligent sampling for multiple change-points in exceedingly long time series with rate guarantees
• Moving sum data segmentation for stochastics processes based on invariance

Cited by in corpus (1)

• Moving sum data segmentation for stochastics processes based on invariance