Wild binary segmentation for multiple change-point detection

By Piotr Fryzlewicz. 2014

756 citations recorded by the source corpus.

We propose a new technique, called wild binary segmentation (WBS), for consistent estimation of the number and locations of multiple change-points in data. We assume that the number of change-points can increase to infinity with the sample size. Due to a certain random localisation mechanism, WBS works even for very short spacings between the change-points and/or very small jump magnitudes, unlike standard binary segmentation. On the other hand, despite its use of localisation, WBS does not require the choice of a window or span parameter, and does not lead to a significant increase in computational complexity. WBS is also easy to code. We propose two stopping criteria for WBS: one based on thresholding and the other based on what we term the `strengthened Schwarz information criterion'. We provide default recommended values of the parameters of the procedure and show that it offers very good practical performance in comparison with the state of the art. The WBS methodology is implemented in the R package wbs, available on CRAN. In addition, we provide a new proof of consistency of binary segmentation with improved rates of convergence, as well as a corresponding result for WBS.

Subfields: Artificial Intelligence, Statistics and Probability, Signal Processing

View Paper: https://www.semanticscholar.org/paper/ca14a857503ef4cdfe8f266c3061161d4f49f69b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Signal Processing

Citations in the corpus

Change-point detection in panel data via double CUSUM statistic (2016, methodology): “The following proof is an adaptation of the proof of Theorem 3.3.1 in Fryzlewicz (2014) to a non-i.i.d. case.”
Testing relevant hypotheses in functional time series via self‐normalization (2018, methodology): “For testing either of the hypotheses, we propose to first estimate the multiple change points by adapting one of the commonly used methods such as binary segmentation or wild binary segmentation [see for example Vostrikova (1981); Harchaoui and Lévy-Leduc (2010); Fryzlewicz (2014); Zhang and Lavitas”
Finite sample change point inference and identification for high‐dimensional mean vectors (2017, methodology): “Assumptions (a)–(c) are standard signal separation and strength requirements in estimating the multiple change point locations via binary segmentation, see for example, Theorem 1 in Fryzlewicz (2014).”
A review of change point detection methods (2018, methodology): “Applications of BinSeg range from financial time series [9, 32, 33, 52, 92] to context recognition for mobile devices [67] and array-based DNA copy number data [106, 112].”
Inference for single and multiple change‐points in time series (2013, methodology): “One may also see Fryzlewicz (2012) for wild binary segmentation algorithm, which is developed so as to address the situation where the number of change-points may tend to infinity along with the data size.”
Selective review of offline change point detection methods (2020, methodology): “Wild binary search is combined with 805 cL2 C2 to detect mean-shifts of univariate piecewise constant signals (up 806 to 2000 samples) [128].”
Univariate mean change point detection: Penalization, CUSUM and optimality (2018, methodology): “In the last few years, a considerable amount of eﬀorts have been made into developing variants of BS in order to handle multiple change points scenarios, see e.g. Fryzlewicz (2014), Baranowski et al. (2016) and Eichinger and Kirch (2018).”
Multiple‐change‐point detection for high dimensional time series via sparsified binary segmentation (2015, methodology): “This was achieved by adapting, to the high dimensional time series context, the proof techniques from Fryzlewicz (2014) for the univariate signal plus independent, identically distributed (IID) Gaussian noise model.”
Heterogeneous change point inference (2015, background): “1) and in related models are vast, see for instance (Yao, 1988; Donoho and Johnstone, 1994; Csörgo and Horváth, 1997; Bai and Perron, 1998; Braun et al., 2000; Birgé and Massart, 2001; Kolaczyk and Nowak, 2005; Boysen et al., 2009; Harchaoui and Lévy-Leduc, 2010; Jeng et al., 2010; Killick et al., 2”
Exact post-selection inference for the generalized lasso path (2018, background): “It is not hard to show that the selection events associated with many such methods—like binary segmentation, wild binary segmentation of Fryzlewicz [14], and all wavelet thresholding procedures (provided that soft-or hard-thresholding is used)—can be characterized as polyhedral sets in the data y .”
A MOSUM procedure for the estimation of multiple random change points (2018, methodology): “We will now show how the procedure works using some examples from [18] with i.”
Detection of change in the spatiotemporal mean function (2017, background): “Keywords: Change point; Functional data; Mean function; Spatiotemporal data”
Detecting Changes in Slope With an L0 Penalty (2017, methodology): “…is currently one of the most active research areas in statistics due to its importance across a wide range of applications, including: finance (Fryzlewicz 2014); bioinformatics (Futschik et al. 2014); environmental science (Killick et al. 2010); target tracking (Nemeth, Fearnhead, and…”
Detection of Multiple Structural Breaks in Multivariate Time Series (2013, methodology): “Moreover, these methods are particularly designed to detect one structural break and the application of the binary segmentation algorithm (see Vostrikova 1981) is used to locate multiple break points (see, e.g., Fryzlewicz (2012) for a very recent approach).”
Simultaneous multiple change-point and factor analysis for high-dimensional time series (2016, neutral): “The treatment of such approximately piecewise stationary ft and t is similar to that in Fryzlewicz and Subba Rao (2014). Note that the literature on factor models with structural breaks have primarily focused on the case of a single change-point in the loadings or factor number see e.”