  This paper addresses the problem of localizing change points in
high-dimensional linear regression models with piecewise constant regression
coefficients. We develop a dynamic programming approach to estimate the
locations of the change points whose performance improves upon the current
state-of-the-art, even as the dimensionality, the sparsity of the regression
coefficients, the temporal spacing between two consecutive change points, and
the magnitude of the difference of two consecutive regression coefficient
vectors are allowed to vary with the sample size. Furthermore, we devise a
computationally-efficient refinement procedure that provably reduces the
localization error of preliminary estimates of the change points. We
demonstrate minimax lower bounds on the localization error that nearly match
the upper bound on the localization error of our methodology and show that the
signal-to-noise condition we impose is essentially the weakest possible based
on information-theoretic arguments. Extensive numerical results support our
theoretical findings, and experiments on real air quality data reveal change
points supported by historical information not used by the algorithm.
