A Fast Multiple Change-Point Detection Method via Generalized Nearly Isotonic Optimization

In this paper, we study the generalized nearly isotonic optimization (GNIO) model and its dynamic programming solution (GNIO-DP). We introduce randomness into the GNIO-DP algorithm, enabling its first application to change-point detection and resulting in an O(n) complexity multiple change-point detection method. At the same time, we provide the theoretical properties of the change-point detection and prove the reliability and effectiveness of the GNIO-DP algorithm for this task. The simulation results show that our method has strong change-point detection ability. Compared with traditional methods, our method is faster in most scenarios.