Guillem Rigaill. Pruned dynamic programming for optimal multiple
change-point detection. http://arxiv.org/abs/1004.0887

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.


Kevin Bleakley and Jean-Philippe Vert. Fast methods for change-point
detection in single or multiple profiles

In this talk we will discuss two recent works for the detection of
change-points in noisy piecewise constant profiles.
1) When a single profile is considered, we consider the problem of
approximating a signal by a piecewise-constant function that minimizes a
sum-of-square approximation error penalized by a total variation penalty.
Harchaoui and Levy-Leduc (NIPS 2008) reformulated the problem as a LASSO
regression problem and showed that finding k breakpoints in a signal of
length n takes O(n*k) using the LARS algorithm. Here we show that the
solution can in fact be found in O(n*ln(k)) with a dichotomic segmentation
approach.
2) When several profiles are considered jointly, we propose to detect joint
breakpoints by extending the total-variation based penalty to multiple
dimensions. The resulting estimator is formulated as the solution of a group
LASSO problem, which we propose to approximate by a fast group LARS
procedure in O(n*k*p) to find k breakpoints in n p-dimensional profiles. We
illustrate the use of this method to detect genomic regions of frequent
amplifications and deletion in cancer tumors from comparative genomic
hybridization profiles.