Segmentation of binary sequence via minimizing least square error with total variation regularization

In this paper, we propose a data-driven procedure to segment a binary sequence as an alternative to the popular hidden Markov model (HMM) based procedure.Unlike the HMM, our procedure does not make any distributional or model assumption to the data.To segment the sequence, we suggest to minimize the least square distance from the observations under total variation regularization to the solution, and develop a polynomial time algorithm for it.Finally, we illustrate the algorithm using a toy example and apply it to the Gemini boat race data between Oxford and Cambridge University.Further, we numerically compare the performance of our procedure to the HMM based segmentation through these examples.