Anass Belcaid

The problem of change point detection can be solved either by online methods, based on a discrepancy measure, or by offline methods. The former tries to detect the change points one by one with a sliding window and leads to a lower computational time but are more sensitive to noise. Conversely, offline methods consider the entire data to detect all the change points which make them more robust against the noise but at a price of higher computational cost. In this paper, we propose an operational search method that combines the benefits of both approaches with the double aim to get higher noise resistance while keeping a blazingly fast time. The search method slides over the edges of the signal to determines their state by considering a global constrained energy. Thanks to the calculus of variation, the computation of this energy is reduced to the estimation of the effective jump for each edge. We study the performance and accuracy of our energy variation method to detect the change points in synthetic and real-world examples. The results compare favorably against state of the art algorithm in terms of speed and accuracy.

In this paper, we focus on the problem of change point detection in piecewise constant signals. This problem is central to several applications such as human activity analysis, speech or image analysis and anomaly detection in genetics. We present a novel window-sliding algorithm for an online change point detection. The proposed approach considers a local blanket of a global Markov Random Field (MRF) representing the signal and its noisy observation. For each window, we define and solve the local energy minimization problem to deduce the gradient on each edge of the MRF graph. The gradient is then processed by an activation function to filter the weak features and produce the final jumps. We demonstrate the effectiveness of our method by comparing its running time and several detection metrics with state of the art algorithms.

The problem of denoising piecewise constant signals while preserving their jumps is a challenging problem that arises in many scientific areas. Several denoising algorithms exist such as total variation, convex relaxation, Markov random fields models, etc. The DPS algorithm is a combinatorial algorithm that excels the classical GNC in term of speed and SNR resistance. However, its running time slows down considerably for large signals. The main reason for this bottleneck is the size and the number of linear systems that need to be solved. We develop a recursive implementation of the DPS algorithm that uses the conditional independence, created by a confirmed discontinuity between two parts, to separate the reconstruction process of each part. Additionally, we propose an accelerated Cholesky solver which reduces the computational cost and memory usage. We evaluate the new implementation on a set of synthetic and real world examples to compare the quality of our solver. The results show a significant speed up, especially with a higher number of discontinuities.