Statistics – Computation
Scientific paper
2010-04-06
Statistics
Computation
9 pages
Scientific paper
Multiple change-point detection models assume that the observed data is a realization of an independent random process affected by K-1 abrupt changes, called change-points, at some unknown positions. For off-line detection a dynamic programming (DP) algorithm retrieves the K-1 change-points minimizing the quadratic loss and reduces the complexity from \Theta(n^K) to \Theta(Kn^2) where n is the number of observations. The quadratic complexity in n still restricts the use of such an algorithm to small or intermediate values of n. We propose a pruned DP algorithm that recovers the optimal solution. We demonstrate that at worst the complexity is in O(Kn^2) time and O(Kn) space and is therefore at worst equivalent to the classical DP algorithm. We show empirically that the run-time of our proposed algorithm is drastically reduced compared to the classical DP algorithm. More precisely, our algorithm is able to process a million points in a matter of minutes compared to several days with the classical DP algorithm. Moreover, the principle of the proposed algorithm can be extended to other convex losses (for example the Poisson loss) and as the algorithm process one observation after the other it could be adapted for on-line problems.
No associations
LandOfFree
Pruned dynamic programming for optimal multiple change-point detection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Pruned dynamic programming for optimal multiple change-point detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pruned dynamic programming for optimal multiple change-point detection will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-57712