A Caltech Library Service

High-dimensional change-point estimation: Combining filtering with convex optimization

Soh, Yong Sheng and Chandrasekaran, Venkat (2015) High-dimensional change-point estimation: Combining filtering with convex optimization. In: 2015 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, pp. 151-155. ISBN 978-1-4673-7704-1.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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. A full version of this paper is available online [1].

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle ItemJournal Article Paper
Soh, Yong Sheng0000-0003-3367-1401
Additional Information:© 2015 IEEE.
Subject Keywords:High-dimensional time series; convex geometry;atomic norm thresholding; filtered derivative
Record Number:CaltechAUTHORS:20151007-111059602
Persistent URL:
Official Citation:Soh, Yong Sheng; Chandrasekaran, Venkat, "High-dimensional change-point estimation: Combining filtering with convex optimization," in Information Theory (ISIT), 2015 IEEE International Symposium on , vol., no., pp.151-155, 14-19 June 2015 doi: 10.1109/ISIT.2015.7282435
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:60874
Deposited By: Tony Diaz
Deposited On:07 Oct 2015 19:11
Last Modified:10 Nov 2021 22:40

Repository Staff Only: item control page