  In recent years, there has been an increasing demand on efficient algorithms
for large scale change point detection problems. To this end, we propose seeded
binary segmentation, an approach relying on a deterministic construction of
background intervals, called seeded intervals, in which single change points
are searched. The final selection of change points based on the candidates from
seeded intervals can be done in various ways, adapted to the problem at hand.
Thus, seeded binary segmentation is easy to adapt to a wide range of change
point detection problems, let that be univariate, multivariate or even
high-dimensional.
  We consider the univariate Gaussian change in mean setup in detail. For this
specific case we show that seeded binary segmentation leads to a near-linear
time approach (i.e. linear up to a logarithmic factor) independent of the
underlying number of change points. Furthermore, using appropriate selection
methods, the methodology is shown to be asymptotically minimax optimal. While
computationally more efficient, the finite sample estimation performance
remains competitive compared to state of the art procedures. Moreover, we
illustrate the methodology for high-dimensional settings with an inverse
covariance change point detection problem where our proposal leads to massive
computational gains while still exhibiting good statistical performance.
