Soh, Yong Sheng and Chandrasekaran, Venkat (2017) High-dimensional change-point estimation: Combining filtering with convex optimization. Applied and Computational Harmonic Analysis, 43 (1). pp. 122-147. ISSN 1063-5203. doi:10.1016/j.acha.2015.11.003. https://resolver.caltech.edu/CaltechAUTHORS:20170525-100137066
![]() |
PDF
- Submitted Version
See Usage Policy. 538kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170525-100137066
Abstract
We consider change-point estimation in a sequence of high-dimensional signals given noisy observations. Classical approaches to this problem such as the filtered derivative method are useful for sequences of scalar-valued signals, but they have undesirable scaling behavior in the high-dimensional setting. However, many high-dimensional signals encountered in practice frequently possess latent low-dimensional structure. Motivated by this observation, we propose a technique for high-dimensional change-point estimation that combines the filtered derivative approach from previous work with convex optimization methods based on atomic norm regularization, which are useful for exploiting structure in high-dimensional data. Our algorithm is applicable in online settings as it operates on small portions of the sequence of observations at a time, and it is well-suited to the high-dimensional setting both in terms of computational scalability and of statistical efficiency. The main result of this paper shows that our method performs change-point estimation reliably as long as the product of the smallest-sized change (the Euclidean-norm-squared of the difference between signals at a change-point) and the smallest distance between change-points (number of time instances) is larger than a Gaussian width parameter that characterizes the low-dimensional complexity of the underlying signal sequence.
Item Type: | Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||
ORCID: |
| ||||||||||||
Additional Information: | © 2015 Elsevier Inc. Received 11 December 2014, Revised 3 November 2015, Accepted 6 November 2015, Available online 11 November 2015. This work was supported in part by the following sources: National Science Foundation Career award CCF-1350590, Air Force Office of Scientific Research grant FA9550-14-1-0098, an Okawa Research Grant in Information and Telecommunications, and an A*STAR (Agency for Science, Technology and Research, Singapore) Fellowship. Yong Sheng Soh would like to thank Michael McCoy for useful discussions, and Atul Ingle for pointing out a typographical error in a preliminary version of this paper. The authors would like to thank the reviewers for their useful comments and suggestions. | ||||||||||||
Funders: |
| ||||||||||||
Subject Keywords: | High-dimensional time series; Convex geometry; Atomic norm thresholding; Filtered derivative | ||||||||||||
Issue or Number: | 1 | ||||||||||||
DOI: | 10.1016/j.acha.2015.11.003 | ||||||||||||
Record Number: | CaltechAUTHORS:20170525-100137066 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170525-100137066 | ||||||||||||
Official Citation: | Yong Sheng Soh, Venkat Chandrasekaran, High-dimensional change-point estimation: Combining filtering with convex optimization, Applied and Computational Harmonic Analysis, Volume 43, Issue 1, July 2017, Pages 122-147, ISSN 1063-5203, https://doi.org/10.1016/j.acha.2015.11.003. (http://www.sciencedirect.com/science/article/pii/S1063520315001542) | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 77750 | ||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||
Deposited By: | Tony Diaz | ||||||||||||
Deposited On: | 25 May 2017 18:22 | ||||||||||||
Last Modified: | 15 Nov 2021 17:33 |
Repository Staff Only: item control page