Statistics – Methodology
Scientific paper
2011-01-07
Statistics
Methodology
37 pages, 5 figures, submitted
Scientific paper
We consider the problem of detecting multiple changepoints in large data sets. Our focus is on applications where the number of changepoints will increase as we collect more data: for example in genetics as we sequence larger regions of the genome, or in finance as we observe time-series over longer periods. We consider the common approach of detecting changepoints through minimising a cost function over possible numbers and locations of changepoints. This includes most common procedures for detecting changing points, such as penalised 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, that has a computational cost which, under mild conditions, is linear in the number of observations. This compares favourably with existing methods for the same problem whose computational cost can be quadratic, or even cubic. In simulation studies we show that our new method can be orders of magnitude faster than these alternative methods. We also compare with Binary Segmentation and a genetic algorithm for finding changepoints, and show that the exactness of our approach can lead to substantial improvements in the accuracy of the inferred segmentation of the data.
Eckley I. A.
Fearnhead Paul
Killick R.
No associations
LandOfFree
Optimal detection of changepoints with a linear computational cost does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal detection of changepoints with a linear computational cost, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal detection of changepoints with a linear computational cost will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-483938