  Change-point problems have appeared in a great many applications for example
cancer genetics, econometrics and climate change. Modern multiscale type
segmentation methods are considered to be a statistically efficient approach
for multiple change-point detection, which minimize the number of change-points
under a multiscale side-constraint. The constraint threshold plays a critical
role in balancing the data-fit and model complexity. However, the computation
time of such a threshold is quadratic in terms of sample size $n$, making it
impractical for large scale problems. In this paper we proposed an
$\mathcal{O}(n)$ algorithm by utilizing the hidden quasiconvexity structure of
the problem. It applies to all regression models in exponential family with
arbitrary convex scale penalties. Simulations verify its computational
efficiency and accuracy. An implementation is provided in R-package "linearQ"
on CRAN.
