B1700
Title: Multiple change point detection in high dimensional data streams via the doubling algorithm
Authors: George Michailidis - University of California, Los Angeles (United States) [presenting]
Abstract: The problem of change point detection in high dimensional data has received a lot of attention in the literature, due to numerous applications in engineering, health and social sciences. A number of algorithms have been proposed and their theoretical properties investigated and performance in synthetic and real data sets illustrated. However, in many settings, the presence of a change point is driven by changes across a large number of the data streams under consideration. It is then reasonable to assume that detection of the locations of the underlying change points can be accomplished by examining only a subset of the available data streams, thus leading to significant computational gains. To that end, an algorithm based on binary segmentation is introduced that selects subsets of a certain size of the data streams and compares their detected change points; if there is an agreement, the algorithm stops, otherwise, it selects a fresh subset of data streams, double the sizes of the original ones, and continues in the same fashion until the agreement is reached or all the streams are included. Theoretical properties of the developed doubling algorithm are established and its performance is illustrated through numerical experiments.
