View Submission - CMStatistics

B1853
**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.

Nicolas Deschamps de Boishebert - Evry Paris-Saclay University (France)

Marco Pascucci - Evry Paris-Saclay University (France)

Guillem Rigaill - INRA (France)