An Algorithm for Optimal Partitioning of Data on an Interval
arXiv:math/0309285 · doi:10.1109/LSP.2001.838216
Abstract
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 data points in time . 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.
arXiv comment3 pages, 1 figure, submitted to IEEE Signal Processing Letters, revised version with added references
References in corpus (1)
Cited by in corpus (65)
- The Large Area Telescope on the Fermi Gamma-ray Space Telescope Mission
- Optimal detection of changepoints with a linear computational cost
- The Second Fermi Large Area Telescope Catalog of Gamma-ray Pulsars
- Wild binary segmentation for multiple change-point detection
- 3FHL: The Third Catalog of Hard Fermi-LAT Sources
- 2FHL: The Second Catalog of Hard Fermi-LAT Sources
- Gamma-ray Activity in the Crab Nebula: The Exceptional Flare of April 2011
- Threshold for Extended Emission in Short Gamma-Ray Bursts
- Optimal Data-Based Binning for Histograms
- An adaptive-binning method for generating constant-uncertainty/constant-significance light curves with Fermi-LAT data
- Active Galactic Nuclei under the scrutiny of CTA
- X-ray Super-Flares From Pre-Main Sequence Stars: Flare Energetics And Frequency
- Detecting multiple generalized change-points by isolating single ones
- Constraining the High-Energy Emission from Gamma-ray Bursts with Fermi
- FDR-Control in Multiscale Change-point Segmentation
- Exploratory Analysis of Functional Data via Clustering and Optimal Segmentation
- Data challenges of time domain astronomy
- Gamma-ray heartbeat powered by the microquasar SS 433
- Structure in the 3D Galaxy Distribution: I. Methods and Example Results
- GeV detection of HESS J0632+057
- The GMRT High Resolution Southern Sky Survey for pulsars and transients -II. New discoveries, timing and polarization properties
- A stacked analysis of 115 pulsars observed by the Fermi LAT
- Observing and modeling the gamma-ray emission from pulsar/pulsar wind nebula complex PSR J0205+6449/3C 58
- A linear time method for the detection of point and collective anomalies
- Multiple Change Point Analysis: Fast Implementation And Strong Consistency
- Gamma-ray emission from PSR J0007+7303 using 7 years of Fermi Large Area Telescope observations
- Data segmentation algorithms: Univariate mean change and beyond
- Bayesian detection of piecewise linear trends in replicated time-series with application to growth data modelling
- Investigation of gamma-ray variability and glitches of PSR J1420-6048
- Smoothing for signals with discontinuities using higher order Mumford-Shah models
- MAGIC observations of the microquasar V404 Cygni during the 2015 outburst
- Compressing network populations with modal networks reveals structural diversity
- Against the Others! Detecting Moral Outrage inSocial Media Networks
- Computing Accurate Probabilistic Estimates of One-D Entropy from Equiprobable Random Samples
- Online Structural Change-point Detection of High-dimensional Streaming Data via Dynamic Sparse Subspace Learning
- A Bayesian binary algorithm for RMS-based acoustic signal segmentation
- Multiscale Jump Testing and Estimation Under Complex Temporal Dynamics
- Approximate -penalized estimation of piecewise-constant signals on graphs
- Multiple Testing of Local Extrema for Detection of Change Points
- Exact and rapid linear clustering of networks with dynamic programming
- Investigation of the timing and spectral properties of an Ultra-luminous X-ray pulsar NGC 7793 P13
- From BGP to RTT and Beyond: Matching BGP Routing Changes and Network Delay Variations with an Eye on Traceroute Paths
- anomaly : Detection of Anomalous Structure in Time Series Data
- Smoothing splines for discontinuous signals
- Time domain methods for X-ray and gamma-ray astronomy
- Comparison of the Origin of Short Gamma-Ray Bursts with or without Extended Emission
- INTEGRAL/SPI data segmentation to retrieve source intensity variations
- Automatic detection of long-duration transients in Fermi-GBM data
- Structure in Galaxy Distribution. III. Fourier Transforming the Universe
- Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise
- Penalty Learning for Optimal Partitioning using Multilayer Perceptron
- Estimation of multiple change points under a generalised Ornstein-Uhlenbeck framework
- Degrees-of-freedom penalized piecewise regression
- Data-adaptive structural change-point detection via isolation
- Parallelisation of a Common Changepoint Detection Method
- Empirical Bayesian analysis of simultaneous changepoints in multiple data sequences
- Online Multivariate Changepoint Detection: Leveraging Links With Computational Geometry
- Change-in-Slope Optimal Partitioning Algorithm in a Finite-Size Parameter Space
- Constrained variable clustering and the best basis problem in functional data analysis
- Examining a hadronic -ray scenario for the radiative shell & molecular clouds of the old GeV supernova remnant G298.60.0
- An Information-theoretic Framework for the Lossy Compression of Link Streams
- Investigating the emission signatures of pulsar halo candidate HESS J1813-126
- Nonparametric Detection of Multiple Location-Scale Change Points via Wild Binary Segmentation
- Gamma-Ray Millisecond Pulsars: Off-pulse Emission Characteristics, Phase-Resolved Pseudo-Luminosity--Cutoff Energy Correlation, and High-energy Pulsed Emission
- On the future of astrostatistics: statistical foundations and statistical practice