Title: Efficient change-in-slope optimal partitioning algorithm in a finite-size parameter space
Authors: Vincent Runge - Evry Paris-Saclay University (France) [presenting]
Nicolas Deschamps de Boishebert - Evry Paris-Saclay University (France)
Marco Pascucci - Evry Paris-Saclay University (France)
Guillem Rigaill - INRA (France)
Abstract: The problem of detecting change-points in univariate time series is considered by fitting a piecewise linear continuous signal. Values for beginning and ending points of each segment are restricted to a finite set of size $m$. Using this finite parameter space, we write a dynamic programming algorithm with time complexity $O(m^2n^2)$ (for $n$ data points) which is similar to the optimal partitioning approach. Some pruning strategies can be added to reduce the constant before $n^2$. As for functional pruning optimal partitioning, we are able to constrain the inference to an increasing signal (isotonic constraint) to a unimodal signal (up-down constraint) or to a robust (to outliers) signal. Our algorithm was initially developed to analyse beat-per-minute time series in order to build a simplified continuous signal with integer change-points which is the right level of information for musicians.