TAIL-GREEDY BOTTOM-UP DATA DECOMPOSITIONS AND FAST MULTIPLE CHANGE-POINT DETECTION

• 成果类型: Article
• 署名作者: Fryzlewicz, Piotr
• 署名单位: University of London; London School Economics & Political Science
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/17-AOS1662
• 发表日期: 2018
• 页码: 3390-3421
• 关键词: circular binary segmentation; dna-sequence segmentation; least-squares estimation; time-series; information criterion; fused lasso; number; algorithm; selection; MODEL

摘要

This article proposes a tail-greedy, bottom-up transform for one-dimensional data, which results in a nonlinear but conditionally orthonormal, multiscale decomposition of the data with respect to an adaptively chosen unbalanced Haar wavelet basis. The tail-greediness of the decomposition algorithm, whereby multiple greedy steps are taken in a single pass through the data, both enables fast computation and makes the algorithm applicable in the problem of consistent estimation of the number and locations of multiple change-points in data. The resulting agglomerative change-point detection method avoids the disadvantages of the classical divisive binary segmentation, and offers very good practical performance. It is implemented in the R package breakfast, available from CRAN.