Showing 1–1 of 1 results for author: Tsai, T T

An Algorithm for Optimal Partitioning of Data on an Interval

Authors: Brad Jackson, Jeffrey D. Scargle, David Barnes, Sundararajan Arabhi, Alina Alt, Peter Gioumousis, Elyus Gwin, Paungkaew Sangtrakulcharoen, Linda Tan, Tun Tao Tsai

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^2)$. The algorithm is guaranteed to find the exact global optimum, automatically determines the model order (t… ▽ More 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. △ Less

Submitted 9 April, 2004; v1 submitted 17 September, 2003; originally announced September 2003.

Comments: 3 pages, 1 figure, submitted to IEEE Signal Processing Letters, revised version with added references

MSC Class: 65C60