An algorithm for optimal partitioning of data on an interval

By B. Jackson, J. Scargle, David Barnes, Sundararajan Arabhi, A. Alt, Peter Gioumousis, Elyus Gwin, Paungkaew Sangtrakulcharoen, Linda S. L. Tan, Tung-Hau Tsai. IEEE Signal Processing Letters, 2003

440 citations recorded by the source corpus.

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/sup 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.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/d5915129ef07a7cae03e7420d079ac48500449a9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

THE LARGE AREA TELESCOPE ON THE FERMI GAMMA-RAY SPACE TELESCOPE MISSION (2009, methodology): “The refinement task uses a Bayesian Blocks temporal analysis (Scargle 1998; Jackson et al. 2005) to characterize the prompt burst light curve, and from that analysis, it determines the burst start time and duration.”
Inference for single and multiple change‐points in time series (2013, methodology): “Although the computational cost of implementing the Jackson et al. (2005) algorithm is O(n2) for a univariate time series, Killick et al. (2012) found a way of pruning some partitions, which would not contribute to the optimal solution.”
Detecting Changes in Slope With an L0 Penalty (2017, methodology): “onds to an L 0 penalty on the change in the slope of the mean. Dynamic programming can be used to eciently nd the best segmentation of the data under such a criterion for the change in mean problem (Jackson et al., 2005; Killick et al., 2012; Maidstone et al., 2017). Our statistical approach is to u”
GAMMA-RAY ACTIVITY IN THE CRAB NEBULA: THE EXCEPTIONAL FLARE OF 2011 APRIL (2011, methodology): “The algorithm to determine the optimal partition is described by Jackson et al. (2005).”
Optimal detection of changepoints with a linear computational cost (2011, methodology): “This approach is based on the algorithm of Jackson et al. (2005), but involves a pruning step within the dynamic program.”
3FHL: The Third Catalog of Hard Fermi-LAT Sources (2017, background): “The transition between blocks is determined by optimizing a fitness function (using the algorithm of Jackson et al. 2005), which in our case is the logarithm of the likelihood for each individual block under the hypothesis of a constant local flux (Scargle et al. 2013).”
A dynamic programming segmentation procedure for hydrological and environmental time series (2006, methodology): “Dynamic programming has often been used in the past for the segmentation of curves (Bellman 1961) and waveforms (Jackson 2005; Kay 1998; Kay and Han, unpublished manuscript; Pavlidis and Horowitz 1974).”
2FHL: THE SECOND CATALOG OF HARD FERMI-LAT SOURCES (2015, background): “The location of the transition between blocks is determined by optimizing a fitness function (using the algorithm of Jackson et al. 2005) for the partitions.”
Wild binary segmentation for multiple change-point detection (2014, methodology): “…as multi-variate optimisation problems, such as those based on penalised least-squares or log-likelihood ﬁts, is their computational complexity, which is typically of order O ( T 2 ) [see, e.g., Auger and Lawrence (1989) and Jackson et al. (2005)], a prohibitively slow speed for large datasets.”