Optimal Detection of Changepoints with a Linear Computational Cost
Paul Fearnhead (Lancaster University)
Friday 20th September, 2013 15:00-16:00 Maths 204
We consider the problem of detecting multiple changepoints in large datasets, through minimizing a cost function over the possible numbers and locations of changepoints. This includes several established procedures for detecting changing points, such as penalized likelihood and minimum description length. We introduce a new method for finding the minimum of such cost functions and hence the optimal number and location of changepoints. For scenarios where the number of changepoints increases linearly with the amount of data this method has a computational cost, which, under mild conditions, is linear in the number of observations. This compares favorably with existing methods for the same problem whose computational cost can be quadratic or even cubic.
Joint work with Rebecca Killick and Idris Eckley.