Efficient Multiple Change-Point Detection on CAT Spaces

We study the problem of multiple change-point detection (MCP) for time series in non-Euclidean spaces. We consider the change-in-mean problem using an intrinsic notion of mean called Fréchet means. A computationally efficient algorithm that exactly optimizes an l0-penalized criterion is used for inference. The efficiency of this dynamic programming scheme comes from the initialization of a finite set of chosen Fréchet means. For a broad class of geodesic spaces (CAT(κ)-spaces), our statistical analysis shows that the method achieves a minimax-optimal convergence rate of O(1/T ). In addition, we propose and study several strategies for initializing the set of Fréchet means. We demonstrate the efficiency of the MCP algorithm with synthetic datasets arising from various (locally) CAT spaces, including spherical data, data on the Grassmannian manifold, and time series of graphs.