Computationally Efficient Multivariate Changepoint Detection with Subsets

Rebecca Killick (Lancaster University)

Friday 17th January, 2020 15:00-16:00 Maths 311B

Abstract

Historically much of the research on changepoint analysis has focused on the univariate setting.  Due to the growing number of high dimensional datasets there is an increasing need for methods that can detect changepoints in multivariate time series. In this talk 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. The work in this presentation is the first to create a dynamic program specifically for detecting changes in subset-multivariate time series.  The computational complexity of the dynamic program means it is infeasible even for medium datasets.  Thus 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. In small simulation studies we demonstrate that SPOT provides a good approximation to exact methods but is feasible for datasets that contain thousands of variables observed at millions of time points. Furthermore we 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.

Add to your calendar

Download event information as iCalendar file (only this event)