Change-point estimation of high-dimensional streaming data via sketching

Change-point detection is of great interest in applications such as target tracking, anomaly detection and trend filtering. In many cases, it is also desirable to localize the change- point, if it exists. Motivated by the unprecedented scale and rate of modern high-dimensional streaming data, we propose a change-point detection and estimation procedure based on data sketching, which only requires a single sketch per high- dimensional data vector, by cyclically applying a small set of Gaussian sketching vectors. We demonstrate that when the underlying changes exhibit certain low-dimensional structures, such as sparsity, and the signal-to-noise ratio is not too small, the change-points can be reliably detected and located with a small number of sketching vectors based on filtering via convex optimization. Our procedure can be implemented in an online fashion to handle multiple change-points, since it sequentially operates on small windows of observations.