An Algorithm for Optimal Partitioning of Data on an Interval
<|reference_start|>An Algorithm for Optimal Partitioning of Data on an Interval: Many signal processing problems can be solved by maximizing the fitness of a segmented model over all possible partitions of the data interval. This letter describes a simple but powerful algorithm that searches the exponentially large space of partitions of $N$ data points in time $O(N^2)$. The algorithm is guaranteed to find the exact global optimum, automatically determines the model order (the number of segments), has a convenient real-time mode, can be extended to higher dimensional data spaces, and solves a surprising variety of problems in signal detection and characterization, density estimation, cluster analysis and classification.<|reference_end|>
@article{jackson2003an,
    title={An Algorithm for Optimal Partitioning of Data on an Interval},
    author={Brad Jackson, Jeffrey D. Scargle, David Barnes, Sundararajan Arabhi,
  Alina Alt, Peter Gioumousis, Elyus Gwin, Paungkaew Sangtrakulcharoen, Linda
  Tan, and Tun Tao Tsai},
    journal={arXiv preprint arXiv:math/0309285},
    year={2003},
    doi={10.1109/LSP.2001.838216},
    archivePrefix={arXiv},
    eprint={math/0309285},
    primaryClass={math.NA astro-ph cs.CE cs.DS cs.IT math.CO math.IT}
}