## Greedy Gaussian Segmentation of Multivariate Time SeriesD. Hallac, P. Nystrup, and S. Boyd
Manuscript, October 2016, updated June 2017 and January 2018. We consider the problem of breaking a multivariate (vector) time series into
segments over which the data is well explained as independent samples
from a Gaussian distribution.
We formulate this as a covariance-regularized maximum likelihood problem,
which can be reduced to a combinatorial optimization problem of
searching over the possible breakpoints, or segment boundaries.
This problem can be solved using dynamic programming, with complexity
that grows with the square of the time series length.
We propose a heuristic method with linear complexity in the time
series length, that approximately solves the problem,
and always yields a locally optimal choice, in the sense that no change of
any one breakpoint improves the objective.
Our method, which we call |