Title :
An algorithm for optimal partitioning of data on an interval
Author :
Jackson, B. ; Scargle, J.D. ; Barnes, D. ; Arabhi, S. ; Alt, A. ; Gioumousis, P. ; Gwin, E. ; Sangtrakulcharoen, P. ; Tan, L. ; Tun Tao Tsai
Author_Institution :
Dept. of Math., San Jose State Univ., CA, USA
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 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.
Keywords :
density measurement; pattern clustering; signal detection; statistical analysis; cluster analysis; density estimation; exact global optimum; higher dimensional data spaces; optimal data partitioning; signal detection; signal processing problems; Algorithm design and analysis; Bayesian methods; Clustering algorithms; Iterative algorithms; Mathematics; NASA; Partitioning algorithms; Signal analysis; Signal detection; Signal processing algorithms; Bayesian modeling; cluster analysis; density estimation; histograms; optimization; signal detection;
Journal_Title :
Signal Processing Letters, IEEE
DOI :
10.1109/LSP.2001.838216
