Seeded Binary Segmentation: A general methodology for fast and optimal change point detection

Abstract

In recent years, there has been an increasing demand on efficient algorithms for large scale change point detection problems. To this end, we propose seeded binary segmentation, an approach relying on a deterministic construction of background intervals, called seeded intervals, in which single change points are searched. The final selection of change points based on the candidates from seeded intervals can be done in various ways, adapted to the problem at hand. Thus, seeded binary segmentation is easy to adapt to a wide range of change point detection problems, let that be univariate, multivariate or even high-dimensional. We consider the univariate Gaussian change in mean setup in detail. For this specific case we show that seeded binary segmentation leads to a near-linear time approach (i.e. linear up to a logarithmic factor) independent of the underlying number of change points. Furthermore, using appropriate selection methods, the methodology is shown to be asymptotically minimax optimal. While computationally more efficient, the finite sample estimation performance remains competitive compared to state of the art procedures. Moreover, we illustrate the methodology for high-dimensional settings with an inverse covariance change point detection problem where our proposal leads to massive computational gains while still exhibiting good statistical performance.

References in corpus (20)

• Optimal detection of changepoints with a linear computational cost
• Wild binary segmentation for multiple change-point detection
• Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
• Exact covariance thresholding into connected components for large-scale Graphical Lasso
• Consistencies and rates of convergence of jump-penalized least squares estimators
• Optimal and fast detection of spatial clusters with scan statistics
• Regularized Estimation of Piecewise Constant Gaussian Graphical Models: The Group-Fused Graphical Lasso
• Change-point detection in high-dimensional covariance structure
• FDR-Control in Multiscale Change-point Segmentation
• Computationally efficient change point detection for high-dimensional regression
• Optimal Covariance Change Point Localization in High Dimension
• Statistically and Computationally Efficient Change Point Localization in Regression Settings
• Optimal nonparametric change point detection and localization
• Multiscale Change-point Segmentation: Beyond Step Functions
• Optimal detection of multi-sample aligned sparse signals
• Multi-sequence segmentation via score and higher-criticism tests
• Multiple Changepoint Estimation in High-Dimensional Gaussian Graphical Models
• Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality
• Intelligent sampling for multiple change-points in exceedingly long time series with rate guarantees
• Seeded intervals and noise level estimation in change point detection: A discussion of Fryzlewicz (2020)

Cited by in corpus (12)

• Data segmentation algorithms: Univariate mean change and beyond
• A review on minimax rates in change point detection and localisation
• A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning
• Graphical Elastic Net and Target Matrices: Fast Algorithms and Software for Sparse Precision Matrix Estimation
• fabisearch: A Package for Change Point Detection in and Visualization of the Network Structure of Multivariate High-Dimensional Time Series in R
• Detection and inference of changes in high-dimensional linear regression with non-sparse structures
• Seeded intervals and noise level estimation in change point detection: A discussion of Fryzlewicz (2020)
• Degrees-of-freedom penalized piecewise regression
• Data-adaptive structural change-point detection via isolation
• Online jump and kink detection in segmented linear regression: Statistical optimality meets computational efficiency
• Graph-based multiple change-point detection
• Asymptotic Distribution-free Change-point Detection for Modern Data Based on a New Ranking Scheme