Approximate Recovery in Changepoint Problems, from ${\ell }_2$ Estimation Error Rates

Abstract

In the 1-dimensional multiple changepoint detection problem, we prove that any procedure with a fast enough ${\ell }_2$ error rate, in terms of its estimation of the underlying piecewise constant mean vector, automatically has an (approximate) changepoint screening property---specifically, each true jump in the underlying mean vector has an estimated jump nearby. We also show, again assuming only knowledge of the ${\ell }_2$ error rate, that a simple post-processing step can be used to eliminate spurious estimated changepoints, and thus delivers an (approximate) changepoint recovery property---specifically, in addition to the screening property described above, we are assured that each estimated jump has a true jump nearby. As a special case, we focus on the application of these results to the 1-dimensional fused lasso, i.e., 1-dimensional total variation denoising, and compare the implications with existing results from the literature. We also study extensions to related problems, such as changepoint detection over graphs.

43 pages, 8 figures

References in corpus (4)

• Multiscale inference about a density
• Optimal rates for total variation denoising
• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• On pattern recovery of the fused Lasso

Cited by in corpus (8)

• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Multiscale Change-point Segmentation: Beyond Step Functions
• Adaptive Risk Bounds in Univariate Total Variation Denoising and Trend Filtering
• A review on minimax rates in change point detection and localisation
• Approximate $l_0$-penalized estimation of piecewise-constant signals on graphs
• Change-point detection in a linear model by adaptive fused quantile method
• Sequential (Quickest) Change Detection: Classical Results and New Directions