Multiple Change Points Detection in High-Dimensional Multivariate Regression

doi:10.1007/s11424-022-1205-6

Journal of Systems Science and Complexity ›› 2022, Vol. 35 ›› Issue (6): 2278-2301.DOI: 10.1007/s11424-022-1205-6

Previous Articles Next Articles

Multiple Change Points Detection in High-Dimensional Multivariate Regression

MA Xiaoyan¹, ZHOU Qin², ZI Xuemin³

1. School of Statistics and Data Science, LPMC and KLMDASR, Nankai University, Tianjin 300071, China;
2. School of Statistics and Data Science, LPMC and KLMDASR, Nankai University, Tianjin 300071, China;
3. School of Science, Tianjin University of Technology and Education, Tianjin 300222, China

Received:2021-06-20 Revised:2021-08-25 Online:2022-11-25 Published:2022-12-23
Contact: ZI Xuemin,Email:zi_xuemin@aliyun.com
Supported by:
This research was supported by the National Nature Science Foundation of China under Grant Nos. 11771332, 11771220, 11671178, 11925106, 11971247, and the Nature Science Foundation of Tianjin under Grant No. 18JCJQJC46000. Ma was also supported by the Fundamental Research Funds for the Central Universities.

PDF ( 3 ) Cited

MA Xiaoyan, ZHOU Qin, ZI Xuemin. Multiple Change Points Detection in High-Dimensional Multivariate Regression[J]. Journal of Systems Science and Complexity, 2022, 35(6): 2278-2301.

This paper considers the problem of detecting structural changes in a high-dimensional regression setting. The structural parameters are subject to abrupt changes of unknown magnitudes at unknown locations. The authors propose a new procedure that minimizes a penalized least-squares loss function via a dynamic programming algorithm for estimating the locations of change points. To alleviate the computational burden, the authors adopt a prescreening procedure by eliminating a large number of irrelevant points before implementing estimation procedure. The number of change points is determined via Schwarz's information criterion. Under mild assumptions, the authors establish the consistency of the proposed estimators, and further provide error bounds for estimated parameters which achieve almost-optimal rate. Simulation studies show that the proposed method performs reasonably well in terms of estimation accuracy, and a real data example is used for illustration.

Key words: Consistency, dynamic programming, low-rank structure, multi-task learning, nuclear norm

[1] Bai J, Common breaks in beans and variances for panel data, Journal of Econometrics, 2010, 157: 78–92.
[2] Lee S, Seo M H, and Shin Y, The lasso for high dimensional regression with a possible change point, Journal of the Royal Statistical Society, Series B, 2016, 78: 193–210.
[3] Kaul A, Jandhyala V, and Fotopoulos S, An efficient two step algorithm for high dimensional change point regression models without grid search, Journal of Machine Research, 2019, 20: 1–40.
[4] Yuan M, Ekici A, Lu Z, et al., Dimension reduction and coefficient estimation in multivariate linear regression, Journal of the Royal Statistical Society, Series B, 2007, 69: 329–346.
[5] Chen K, Dong H, and Chan K S, Reduced rank regression via adaptive nuclear norm penalization, Biometrika, 2013, 100(4): 901–920.
[6] Bing X and Wegkamp M H, Adaptive estimation of the rank of the coefficient matrix in highdimensional multivariate response regression models, The Annals of Statistics, 2019, 47: 3157– 3184.
[7] Raskutti G, Yuan M, and Chen H, Convex regularization for high-dimensional multiresponse tensor regression, The Annals of Statistics, 2019, 47: 1554–1584.
[8] Zou C, Ke Y, and Zhang W, Estimation of low rank high dimensional multivariate linear models for multi-response data, Journal of the American Statistical Association, 2022, 117: 693–703.
[9] Chen K, Chan K S, and Stenseth N C, Reduced rank stochastic regression with a sparse singular value decomposition, Journal of the Royal Statistical Society, Series B, 2012, 74: 203–221.
[10] Leonardi F and Bühlmann P, Computationally efficient change point detection for highdimensional regression, arXiv: 1601.03704, 2016.
[11] Zhang B, Geng J, and Lai L, Multiple change-points estimation in linear regression models via sparse group lasso, IEEE Trans. Signal Processing, 2015, 63(9): 2209–2224.
[12] Wang D, Lin K, and Willett R, Statistically and computationally efficient change point localization in regression settings, arXiv: 1906.11364v1, 2019.
[13] Candès E J and Recht B, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 2009, 9: 717–772.
[14] Zhou H and Li L, Regularized matrix regression, Journal of the Royal Statistical Society, Series B, 2014, 76: 463–483.
[15] Nesterov Y, A method of solving a convex programming problem with convergence rate O(1/k²), Soviet Mathematics Doklady, 1983, 27: 372–376.
[16] Beck A and Teboulle M, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2009, 2: 183–202.
[17] Bai J and Perron P, Computation and analysis of multiple structural changes models, Journal of Applied Econometrics, 2003, 18: 1–22.
[18] Killick R, Fearnhead P, and Eckley I A, Optimal detection of changepoints with a linear computational cost, Journal of the American Statistical Association, 2012, 107: 1590–1598.
[19] Scott A G and Knott M, A cluster analysis method for grouping means in the analysis of variance, Biometrics, 1974, 30: 507–512.
[20] Fryzlewicz P, Wild binary segmentation for multiple change-point detection, The Annals of Statistics, 2014, 42: 2243–2281.
[21] Negahban S and Wainwright M J, Estimation of (near) low-rank matrices with noise and highdimensional scaling, The Annals of Statistics, 2011, 39: 1069–1097.
[22] Bickel P, Ritov Y, and Tsybakov A, Simultaneous analysis of lasso and Dantzig selector, The Annals of Statistics, 2009, 37: 1705–1732.
[23] Negahban S N, Ravikumar P, Wainwright M J, et al., A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers, Statistical Science, 2012, 27: 538–557.
[24] Wainwright M J, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge University Press, Cambridge, 2019.
[25] Reinsel G C and Velu R P, Multivariate Reduced Rank Regression Theory and Applications, Springer, New York, 1998.
[26] Chen K, Dong H, and Chan K, Reduced rank regression via adaptive nuclear norm penalization, Biometrika, 2013, 100(4): 901–920.
[27] Boysen L, Kempe A, Liebscher V, et al., Consistencies and rates of convergence of jump-penalized least squares estimators, The Annals of Statistics, 2009, 37: 157–183.
[28] Zou C, Yin G, Feng L, et al., Nonparametric maximum likelihood approach to multiple changepoint problems, The Annals of Statistics, 2014, 42: 970–1002.
[29] Recht B, Fazel M, and Parrilo P A, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 2010, 52: 471–501.
[30] Vershynin R, Introduction to the non-asymptotic analysis of random matrices, arXiv: 1011.3027, 2010.

[1]	ZHANG Liangquan. A BSDE Approach to Stochastic Differential Games Involving Impulse Controls and HJBI Equation [J]. Journal of Systems Science and Complexity, 2022, 35(3): 766-801.
[2]	LUO Jing, QIN Hong. Asymptotic in the Ordered Networks with a Noisy Degree Sequence [J]. Journal of Systems Science and Complexity, 2022, 35(3): 1137-1153.
[3]	PENG Yunjie, ZHENG Xiaoqian, YU Wei, HE Kaixin, WANG Xuejun. Strong Law of Large Numbers for Weighted Sums of Random Variables and Its Applications in EV Regression Models [J]. Journal of Systems Science and Complexity, 2022, 35(1): 342-360.
[4]	JIANG Yanguang,HUANG Yi,XUE Wenchao,FANG Haitao. On Designing Consistent Extended Kalman Filter [J]. Journal of Systems Science and Complexity, 2017, 30(4): 751-764.
[5]	LI Juan,MIN Hui. Controlled Mean-Field Backward Stochastic Differential Equations with Jumps Involving the Value Function [J]. Journal of Systems Science and Complexity, 2016, 29(5): 1238-1268.
[6]	FAN Yan,GAI Yujie,ZHU Lixing. Asymtotics of Dantzig Selector for a General Single-Index Model [J]. Journal of Systems Science and Complexity, 2016, 29(4): 1123-1144.
[7]	LI Danping,RONG Ximin,ZHAO Hui. Time-Consistent Investment Strategy for DC Pension Plan with Stochastic Salary Under CEV Model [J]. Journal of Systems Science and Complexity, 2016, 29(2): 428-454.
[8]	WEI Qi,KANG Liying,SHAN Erfang. Batching Scheduling in a Two-Level Supply Chain with Earliness and Tardiness Penalties [J]. Journal of Systems Science and Complexity, 2016, 29(2): 478-498.
[9]	JIANG Yu, JIANG Zhong-Ping. A Robust Adaptive Dynamic Programming Principle for Sensorimotor Control with Signal-Dependent Noise [J]. Journal of Systems Science and Complexity, 2015, 28(2): 261-288.
[10]	HUANG Rui, CUI Hengjian. Consistency of Chi-Squared Test with Varying Number of Classes [J]. Journal of Systems Science and Complexity, 2015, 28(2): 439-450.
[11]	CHANG Hao , CHANG Kai. LEGENDRE TRANSFORM-DUAL SOLUTION FOR INVESTMENT AND CONSUMPTION PROBLEM UNDER THE VASICEK MODEL [J]. Journal of Systems Science and Complexity, 2014, 27(5): 911-927.
[12]	ZHANG Jie , NIU Baozhuang , LI Jianbin. OPTIMAL PRICING AND INVENTORY POLICY WITH ORDER CANCELATIONS UNDER THE CASH-ON-DELIVERY PAYMENT SCHEME [J]. Journal of Systems Science and Complexity, 2014, 27(5): 970-992.
[13]	Huixiu ZHAO, Jinguan LIN. THE LARGE SAMPLE PROPERTIES OF THE SOLUTIONS OF GENERAL ESTIMATING EQUATIONS [J]. Journal of Systems Science and Complexity, 2012, 25(2): 315-328.
[14]	Qunying WU. FURTHER STUDY STRONG CONSISTENCY OF$M$ ESTIMATOR IN LINEAR MODEL FOR $\widetilde{\rho}$-MIXING RANDOM SAMPLES [J]. Journal of Systems Science and Complexity, 2011, 24(5): 969-980.
[15]	Huiling WU;Zhongfei LI. MULTI-PERIOD MEAN-VARIANCE PORTFOLIO SELECTION WITH MARKOVREGIME SWITCHING AND UNCERTAIN TIME-HORIZON [J]. Journal of Systems Science and Complexity, 2011, 24(1): 140-155.

Viewed

Full text

Abstract