On change-point estimation under Sobolev sparsity. (English) Zbl 1439.62152

Summary: In this paper, we consider the estimation of a change-point for possibly high-dimensional data in a Gaussian model, using a maximum likelihood method. We are interested in how dimension reduction can affect the performance of the method. We provide an estimator of the change-point that has a minimax rate of convergence, up to a logarithmic factor. The minimax rate is in fact composed of a fast rate – dimension-invariant – and a slow rate – increasing with the dimension. Moreover, it is proved that considering the case of sparse data, with a Sobolev regularity, there is a bound on the separation of the regimes above which there exists an optimal choice of dimension reduction, leading to the fast rate of estimation. We propose an adaptive dimension reduction procedure based on Lepski’s method and show that the resulting estimator attains the fast rate of convergence. Our results are then illustrated by a simulation study. In particular, practical strategies are suggested to perform dimension reduction.


62H30 Classification and discrimination; cluster analysis (statistical aspects)
62G05 Nonparametric estimation
62G10 Nonparametric hypothesis testing
62C20 Minimax procedures in statistical decision theory


wbs; EBayesThresh
Full Text: DOI Euclid


[1] S. Arlot and A. Celisse. Segmentation of the mean of heteroscedastic data via cross-validation., Stat. Comput., 21(4):613-632, 2011. ISSN 0960-3174. · Zbl 1221.62061
[2] J. A. D. Aston and C. Kirch. Evaluating stationarity via change-point alternatives with applications to fmri data., Ann. Appl. Stat., 6(4) :1906-1948, 2012. · Zbl 1257.62072
[3] A. Aue, S. Hörmann, L. Horváth, M. Reimherr, et al. Break detection in the covariance structure of multivariate time series models., The Annals of Statistics, 37(6B) :4046-4087, 2009. · Zbl 1191.62143
[4] J. Bai. Least square estimation of a shift in linear processes., Journal of Time Series Analysis, 15:453-472, 1994. · Zbl 0808.62079
[5] J. Bai. Common breaks in means and variances for panel data., Journal of Econometrics, 157(1):78-92, 2010. · Zbl 1431.62353
[6] J. Bai and P. Perron. Estimating and testing linear models with multiple structural changes., Econometrica, 66:47-78, 1998. · Zbl 1056.62523
[7] M. Basseville and I. Nikiforov., Detection of abrupt changes: Theory and applications. Lecture Notes in Mathematics. Prentice Hall, 1993. · Zbl 1407.62012
[8] K. Bleakley and J. P. Vert. The group fused Lasso for multiple change-point detection, 2011. Available at, https://hal.inria.fr/hal-00602121.
[9] S. Bourguignon, D. Mary, and E. Slezak. Restoration of astrophysical spectra with sparsity constraints: models and algorithms., J. Sel. Topics Signal Processing, 5 :1002-1013, 2011.
[10] B. E. Brodsky and B. S. Darkhovsky., Nonparametric methods in change-point problems. The Netherlands, 1993. · Zbl 1274.62512
[11] A. Bücher, I. Kojadinovic, T. Rohmer, and J. Segers. Detecting changes in cross-sectional dependence in multivariate time series., Journal of Multivariate Analysis, 132:111-128, 2014. · Zbl 1360.62451
[12] E. Carlstein, H. Müller, and D. Siegmund, editors., Change-point problems, volume 23. 1994. · Zbl 0942.00037
[13] H. Chen and N. Zhang. Graph-based change-point detection., Ann. Statist., 43:139-176, 2015. · Zbl 1308.62090
[14] H. Cho. Change-point detection in panel data via double cusum statistic., Electron. J. Statist., 10(2) :2000-2038, 2016. · Zbl 1397.62301
[15] H. Cho and P. Fryzlewicz. Multiple-change-point detection for high dimensional time series via sparsified binary segmentation., Journal of the Royal Statistical Society: Series B (Statistical Methodology), 77(2):475-507, 2015. · Zbl 1414.62356
[16] I. Cribben and Y. Yu. Estimating whole-brain dynamics by using spectral clustering., Journal of the Royal Statistical Society: Series C (Applied Statistics), 66(3):607-627.
[17] M. Csörgő and L. Horváth., Limit theorems in change-point analysis. 1997. · Zbl 0884.62023
[18] F. Enikeeva and Z. Harchaoui. High-dimensional change-point detection with sparse alternatives, 2017. Available at, https://hal.inria.fr/hal-00933185. · Zbl 1427.62036
[19] J. Fiosina and M. Fiosins. Resampling-based change point estimation. In J. Gama, E. Bradley, and J. Hollmén, editors, Advances in Intelligent Data Analysis X, pages 150-161, Berlin, Heidelberg, 2011. Springer.
[20] K. Frick, A. Munk, and H. Sieling. Multiscale change point inference., Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(3):495-580, 2014. · Zbl 1411.62065
[21] P. Fryzlewicz et al. Wild binary segmentation for multiple change-point detection., The Annals of Statistics, 42(6) :2243-2281, 2014. · Zbl 1302.62075
[22] Z. Harchaoui, F. Vallet, A. Lung-Yut-Fong, and O. Cappe. A regularized kernel-based approach to unsupervised audio segmentation. In, ICASSP, pages 1665-1668, 2009.
[23] S. Hariz and J. J. Wylie. Rates of convergence for the change-point estimator for long-range dependent sequences., Statistics & Probability Letters, 73:155-164, 06 2005. · Zbl 1081.62061
[24] S. B. Hariz, J. J. Wylie, and Q. Zhang. Optimal rate of convergence for nonparametric change-point estimators for nonstationary sequences., Ann. Statist., 35 :1802-1826, 2007. · Zbl 1147.62043
[25] S. S. Henry, D. and R. J. Patton. Fault detection and diagnosis for aeronautic and aerospace missions. In T. L. C. Edwards and H. Smaili, editors, Fault Tolerant Flight Control – a Benchmark Challenge, pages 91-128, Berlin, 2010. Springer.
[26] L. Horváth and M. Hušková. Change-point detection in panel data., Journal of Time Series Analysis, 33(4):631-648, 2012. · Zbl 1282.62181
[27] L. Horváth and G. Rice. Extensions of some classical methods in change point analysis., Test, 23(2):219-255, 2014. · Zbl 1305.62310
[28] L. Horváth, P. Kokoszka, and J. Steinebach. Testing for changes in multivariate dependent observations with an application to temperature changes., Journal of Multivariate Analysis, 68(1):96-119, 1999. · Zbl 0962.62042
[29] J. Huang, T. Zhang, and D. Metaxas. Learning with structured sparsity, 2009. · Zbl 1280.68169
[30] B. Jin, G. Pan, Q. Yang, and W. Zhou. On high-dimensional change point problem., Science China Mathematics, 59 :2355-2378, 2016. · Zbl 1360.62075
[31] M. Jirak et al. Uniform change point tests in high dimension., The Annals of Statistics, 43(6) :2451-2483, 2015. · Zbl 1327.62467
[32] I. M. Johnstone and B. W. Silverman. Needles and straw in haystacks: empirical Bayes estimates of possibly sparse sequences., Ann. Statist., 32(4) :1594-1649, 2004. ISSN 0090-5364. · Zbl 1047.62008
[33] R. Killick, P. Fearnhead, and I. A. Eckley. Optimal detection of changepoints with a linear computational cost., Journal of the American Statistical Association, 107(500) :1590-1598, 2012. · Zbl 1258.62091
[34] C. Kirch, B. Muhsal, and H. Ombao. Detection of changes in multivariate time series with application to eeg data., Journal of the American Statistical Association, 110(511) :1197-1216, 2015. · Zbl 1378.62072
[35] A. Korostelev and O. Lepski. On a multi-channel change-point problem., Math. Methods Statist., 17(3):187-197, Sep 2008. · Zbl 1231.62151
[36] A. P. Korostelev. On minimax estimation of a discontinuous signal., Theory Probab. Appl., 32:727- 730, 1987. · Zbl 0659.62103
[37] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection., The Annals of Statistics, 28 :1302-1338, 2000. · Zbl 1105.62328
[38] M. Lavielle and E. Moulines. Least-squares estimation of an unknown number of shifts in a time series., Journal of Time Series Analysis, 21:33-59, 2000. · Zbl 0974.62070
[39] M. Lavielle and G. Teyssière. Detection of multiple change-points in multivariate time series., Lithuanian Mathematical Journal, 46:287-306, 2006. · Zbl 1138.62051
[40] O. Lepski. On a problem of adaptive estimation in Gaussian white noise., Theory Probab. Appl., 35:454-466, 1991.
[41] O. Lepski. Asymptotically minimax adaptive estimation. I: Upper bounds. Optimally adaptive estimates., Theory Probab. Appl., 36:682-697, 1992.
[42] O. Lepski. Asymptotically minimax adaptive estimation. II. Schemes without optimal adaptation: Adaptive estimators., Theory Probab. Appl., 37:433-448, 1993.
[43] C. Levy-Leduc and F. Roueff. Detection and localization of change-points in high-dimensional network traffic data., Ann. Appl. Stat., 3:637-662, 2009. · Zbl 1166.62094
[44] A. Lung-Yut-Fong, C. Levy-Leduc, and O. Cappe. Distributed detection/localization of change-points in high-dimensional network traffic data., Stat. Comput., 22:485-496, 2012. · Zbl 1322.62146
[45] C. Meillier, F. Chatelain, O. Michel, R. Bacon, L. Piqueras, R. Bacher, and H. Ayasso. SELFI: an object-based, Bayesian method for faint emission line source detection in MUSE deep eld data cubes., Astronomy and Astrophysics, 588:140A, 2016.
[46] H. Müller. Change-points in nonparametric regression., Ann. Statist., 20:737-671, 1992. · Zbl 0783.62032
[47] A. B. Olshen, E. Venkatraman, R. Lucito, and M. Wigler. Circular binary segmentation for the analysis of array-based dna copy number data., Biostatistics, 5(4):557-572, 2004. · Zbl 1155.62478
[48] H. Ombao, R. Von Sachs, and W. Guo. Slex analysis of multivariate nonstationary time series., Journal of the American Statistical Association, 100(470):519-531, 2005. · Zbl 1117.62407
[49] E. Page. A test for a change in a parameter occurring at an unknown point., Biometrika, 42(3/4):523-527, 1955. · Zbl 0067.11602
[50] P. Preuss, R. Puchstein, and H. Dette. Detection of multiple structural breaks in multivariate time series., Journal of the American Statistical Association, 110(510):654-668, 2015. · Zbl 1373.62454
[51] Y. Ritov. Asymptotic efficient estimation of the change point with unknown distributions., The Annals of Statistics, 18 :1829-1839, 1990. · Zbl 0714.62027
[52] X. Shi, Y. Wu, and C. R. Rao. Consistent and powerful graph-based change-point test for high-dimensional data., Proceedings of the National Academy of Sciences, 114 :3873-3878, 2017. · Zbl 1407.62327
[53] A. N. Shiryaev., Optimal Stopping Rules. New York, 1978. · Zbl 0391.60002
[54] Y. S. Soh and V. Chandrasekaran. High-dimensional change-point estimation: Combining filtering with convex optimization., Applied and Computational Harmonic Analysis, 43(1):122-147, 2017. · Zbl 1366.62182
[55] R. Sparks, T. Keighley, and D. Muscatello. Early warning cusum plans for surveillance of negative binomial daily disease counts., J. Appl. Statist., 37 :1911-1930, 2010.
[56] R. F. R. Suleiman, D. Mary, and A. Ferrari. Dimension reduction for hypothesis testing in worst-case scenarios., IEEE Transactions on Signal Processing, 62 :5973-5986, 2014. · Zbl 1394.94565
[57] A. B. Tsybakov., Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 2008. ISBN 0387790519, 9780387790510. · Zbl 1176.62032
[58] D. Wang, Y. Yu, and A. Rinaldo. Optimal change point detection and localization in sparse dynamic networks. 2018. Available at, https://arxiv.org/abs/1809.09602.
[59] T. Wang and R. J. Samworth. High dimensional change point estimation via sparse projection., Journal of the Royal Statistical Society, Series B (Statistical Methodology), 80:57-83, 2018. · Zbl 1439.62199
[60] N. R. Zhang, D. O. Siegmund, H. Ji, and J. Li. Detecting simultaneous change-points in multiple sequences., Biometrika, 97:631-645, 2010. · Zbl 1195.62168
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.