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 (6)

• Wild binary segmentation for multiple change-point detection
• Consistencies and rates of convergence of jump-penalized least squares estimators
• Optimal and fast detection of spatial clusters with scan statistics
• Optimal nonparametric change point detection and localization
• Multiple Changepoint Estimation in High-Dimensional Gaussian Graphical Models
• 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