B1567
Title: Computationally efficient detection of subset multivariate changepoints
Authors: Sean Ryan - Lancaster University (United Kingdom) [presenting]
Rebecca Killick - Lancaster University (United Kingdom)
Abstract: Due to the growing number of high dimensional datasets there is an increasing need for methods that can detect changepoints in multivariate time series. We focus on the problem of detecting changepoints where only a subset of the variables under observation undergo a change, so called subset multivariate changepoints. One approach to locating changepoints is to choose the segmentation that minimises a penalised cost function via a dynamic program. While this is possible in our setting, the computational complexity of the algorithm means it is infeasible even for small datasets. We propose a computationally efficient approximate dynamic program, SPOT. We demonstrate that SPOT always recovers a better segmentation, in terms of penalised cost, then other approaches which assume every variable changes. Furthermore, under mild assumptions the computational cost of SPOT is linear in the number of data points. As a result, we are able to apply our method to datasetst with millions of data points and thousands of series. In simulation studies we demonstrate that SPOT provides a good approximation to exact methods. We also demonstrate that our method compares favourably with other commonly used multivariate changepoint methods and achieves a substantial improvement in performance when compared with fully multivariate methods.
