# A log-linear time algorithm for constrained changepoint detection

arXiv: https://arxiv.org/abs/1703.03352 · HTML: https://mlsanity.com/paper/1703.03352/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2017.

## Built on by (most cited first, 2 of 2)

- [A Graph-Constrained Changepoint Learning Approach for Automatic QRS-Complex Detection](https://mlsanity.com/paper/2102.01319/) (2021)
- [A Greedy Graph Search Algorithm Based on Changepoint Analysis for Automatic QRS Complex Detection](https://mlsanity.com/paper/2102.03538/) (2021)

## Abstract (arXiv)

Changepoint detection is a central problem in time series and genomic data. For some applications, it is natural to impose constraints on the directions of changes. One example is ChIP-seq data, for which adding an up-down constraint improves peak detection accuracy, but makes the optimization problem more complicated. We show how a recently proposed functional pruning technique can be adapted to solve such constrained changepoint detection problems. This leads to a new algorithm which can solve problems with arbitrary affine constraints on adjacent segment means, and which has empirical time complexity that is log-linear in the amount of data. This algorithm achieves state-of-the-art accuracy in a benchmark of several genomic data sets, and is orders of magnitude faster than existing algorithms that have similar accuracy. Our implementation is available as the PeakSegPDPA function in the coseg R package, https://github.com/tdhock/coseg