Optimal detection of changepoints with a linear computational cost

Optimal detection of changepoints with a linear computational cost

October 10, 2012 | Killick, R., Fearnhead, P. and Eckley, I.A.*
This paper introduces the Pruned Exact Linear Time (PELT) method for detecting multiple changepoints in large datasets with a computational cost that is linear in the number of observations. The method is exact and efficient, offering significant improvements over existing methods such as Binary Segmentation and Optimal Partitioning. PELT is based on dynamic programming but includes a pruning step that reduces computational cost without affecting the accuracy of the results. It can be applied to various statistical criteria, including penalised likelihood, quasi-likelihood, and cumulative sum of squares. The paper compares PELT with Binary Segmentation and Optimal Partitioning in simulation studies and real-world applications. Results show that PELT is significantly faster than Optimal Partitioning, particularly for large datasets, and more accurate than Binary Segmentation. While Binary Segmentation is faster in some cases, PELT provides more accurate segmentation. The computational cost of PELT is linear in the number of observations under mild conditions, making it suitable for large datasets. The method is applied to oceanographic and financial data, demonstrating its effectiveness in detecting changes in variance and autoregressive models. The paper concludes that PELT offers a computationally efficient and accurate approach for changepoint detection, with statistical benefits outweighing minor computational costs.This paper introduces the Pruned Exact Linear Time (PELT) method for detecting multiple changepoints in large datasets with a computational cost that is linear in the number of observations. The method is exact and efficient, offering significant improvements over existing methods such as Binary Segmentation and Optimal Partitioning. PELT is based on dynamic programming but includes a pruning step that reduces computational cost without affecting the accuracy of the results. It can be applied to various statistical criteria, including penalised likelihood, quasi-likelihood, and cumulative sum of squares. The paper compares PELT with Binary Segmentation and Optimal Partitioning in simulation studies and real-world applications. Results show that PELT is significantly faster than Optimal Partitioning, particularly for large datasets, and more accurate than Binary Segmentation. While Binary Segmentation is faster in some cases, PELT provides more accurate segmentation. The computational cost of PELT is linear in the number of observations under mild conditions, making it suitable for large datasets. The method is applied to oceanographic and financial data, demonstrating its effectiveness in detecting changes in variance and autoregressive models. The paper concludes that PELT offers a computationally efficient and accurate approach for changepoint detection, with statistical benefits outweighing minor computational costs.
Reach us at info@study.space