Fast Algorithm For Multiscale Change Point Segmentation

The change point problem has been widely used in genetic engineering,financial economics,meteorology,and signal processing.And the modern multiscale segmentation algorithm is considered to be a statistically effective method for detecting change points by minimizing the number of change points under a multiscale side constraint.In this paper,we mainly discussed the multiscale change point segmentation.Since the multiscale change point segmentation has high computational cost,we propose new algorithms to improve the operation efficiency.The user-specified constraint threshold plays a critical role in balancing the data-fit and model complexity,usually chosen as the quantile of the null distribution of multiscale statistic.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 introduce a concept from computational geometry and transform the original problem to maximizing a quasiconvex function over the convex hull of a constrained Minkowski sum.We proposed an O(n)algorithm —linearQ.It reduce the original second-order computational complex to first-order.Simulations verify its computational efficiency and accuracy.Besides it applies to all regression models in exponential family with arbitrary concave scale penalties.An implementation is provided in R-package “linearQ” on CRAN.Pruning techniques are often applied in dynamic programming algorithms for solving change point problems.In this paper,a new fast dynamic programming algorithm — fastDP has been proposed,which uses a new pruning method similar to heuristic algorithm — SDP.The SDP provides the boundary for each change point position and thus reduces the research range from all intervals to each small boundary.In the case where the distribution of change points is not very dense,the running cost of the fastDP has nearly linear complexity.Besides,fastDP is more powerful for detecting change points than traditional multiscale estimators.The R-package “OPTS” is under preparation.