Pruned dynamic programming for optimal multiple change-point detection

Abstract

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.