Skip to main content

Advertisement

Springer Nature Link
Log in

A computationally efficient and flexible algorithm for high dimensional mean and covariance matrix change point models

  • Research Article
  • Published:
Journal of the Korean Statistical Society Aims and scope Submit manuscript

Abstract

This paper proposes a computationally efficient algorithm, FBS (Fast Binary Segmentation), for both single and multiple change point detection under high-dimensional setups. As a general technique, it can be widely used in various change point problems including mean vectors and covariance matrices change point models. Based on various \(\ell _{(s,p)}\)-norm aggregations for the cumulative sum (CUSUM) statistics, the new algorithm can be applied to a wide range of alternative structures including sparse and dense settings as special cases. We present the essence of the new algorithm. The efficiency and accuracy of the new algorithm are justified via comparing it with the other existing techniques. Lastly, a real data application further demonstrates the usefulness of our method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  • Aue, A., Hörmann, S., Horváth, L., & Reimherr, M. (2009). Break detection in the covariance structure of multivariate time series models. Annals of Statistics, 37, 4046–4087.

    Article  MathSciNet  MATH  Google Scholar 

  • Avanesov, V., & Buzun, N. (2018). Change-point detection in high-dimensional covariance structure. Electronic Journal of Statistics, 12, 3254–3294.

    Article  MathSciNet  MATH  Google Scholar 

  • Braun, J. V., Braun, R., & Müller, H. G. (2000). Multiple changepoint fitting via quasilikelihood, with application to DNA sequence segmentation. Biometrika, 87, 301–314.

    Article  MathSciNet  MATH  Google Scholar 

  • Bühlmann, P., & Van De Geer, S. (2011). Statistics for high-dimensional data: Methods, theory and applications. Springer Science and Business Media.

    Book  MATH  Google Scholar 

  • Cai, T., & Liu, W. (2011). Adaptive thresholding for sparse covariance matrix estimation. Journal of the American Statistical Association, 106, 672–684.

    Article  MathSciNet  MATH  Google Scholar 

  • Cai, T., Liu, W., & Xia, Y. (2013). Two-sample covariance matrix testing and support recovery in high-dimensional and sparse settings. Journal of the American Statistical Association, 108, 265–277.

    Article  MathSciNet  MATH  Google Scholar 

  • Chang, J., Zheng, C., Zhou, W. X., & Zhou, W. (2017). Simulation-based hypothesis testing of high dimensional means under covariance heterogeneity. Biometrics, 73, 1300–1310.

    Article  MathSciNet  MATH  Google Scholar 

  • Chen, J., & Gupta, A. K. (1997). Testing and locating variance changepoints with application to stock prices. Journal of the American Statistical Association, 92, 739–747.

    Article  MathSciNet  MATH  Google Scholar 

  • Cheng, T. L. (2009). An efficient algorithm for estimating a change-point. Statistics and probability letters, 79, 559–565.

    Article  MathSciNet  MATH  Google Scholar 

  • Cho, H. (2016). Change-point detection in panel data via double CUSUM statistic. Electronic Journal of Statistics, 10, 2000–2038.

    Article  MathSciNet  MATH  Google Scholar 

  • Cho, H., & Fryzlewicz, P. (2015). Multiple-change-point detection for high dimensional time series via sparsified binary segmentation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 77, 475–507.

    Article  MathSciNet  MATH  Google Scholar 

  • Csörgő, M., & Horváth, L. (1997). Limit theorems in change-point analysis. Wiley.

    MATH  Google Scholar 

  • Dette, H., Pan, G., & Yang, Q. (2020). Estimating a change point in a sequence of very high-dimensional covariance matrices. Journal of the American Statistical Association, 0, 1–11.

    Google Scholar 

  • Enikeeva, F., & Harchaoui, Z. (2019). High-dimensional change-point detection under sparse alternatives. Annals of Statistics, 47, 2051–2079.

    Article  MathSciNet  MATH  Google Scholar 

  • Fan, J., Lv, J., & Qi, L. (2011). Sparse high-dimensional models in economics. Annual Review of Economics, 3, 291–317.

    Article  Google Scholar 

  • Fryzlewicz, P. (2014). Wild binary segmentation for multiple change-point detection. The Annals of Statistics, 42, 2243–2281.

    Article  MathSciNet  MATH  Google Scholar 

  • Gao, Z., Shang, Z., Du, P., & Robertson, J. L. (2019). Variance change point detection under a smoothly-changing mean trend with application to liver procurement. Journal of the American Statistical Association, 114, 773–781.

    Article  MathSciNet  MATH  Google Scholar 

  • Gibberd, A. J., & Nelson, J. D. (2017). Regularized estimation of piecewise constant gaussian graphical models: The group-fused graphical lasso. Journal of Computational and Graphical Statistics, 26, 623–634.

    Article  MathSciNet  Google Scholar 

  • Gibberd, A. J., & Roy, S. (2017). Multiple changepoint estimation in high-dimensional gaussian graphical models. arXiv preprint arXiv:1712.05786.

  • Jirak, M. (2015). Uniform change point tests in high dimension. The Annals of Statistics, 43, 2451–2483.

    Article  MathSciNet  MATH  Google Scholar 

  • Kolar, M., & Xing, E. P. (2012). Estimating networks with jumps. Electronic Journal of Statistics, 6, 2069.

    Article  MathSciNet  MATH  Google Scholar 

  • Kovács, S., Li, H., Bühlmann, P., & Munk, A. (2020a). Seeded binary segmentation: A general methodology for fast and optimal change point detection. arXiv preprint arXiv:2002.06633.

  • Kovács, S., Li, H., Haubner, L., Munk, A., & Bühlmann, P. (2020b). Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries. arXiv preprint arXiv:2010.10194.

  • Lavielle, M., & Teyssiére, G. (2006). Detection of multiple change-points in multivariate time series. Lithuanian Mathematical Journal, 46, 287–306.

    Article  MathSciNet  MATH  Google Scholar 

  • Leonardi, F., & Bühlmann, P. (2016). Computationally efficient change point detection for high-dimensional regression. Preprint arXiv:1601.03704.

  • Liu, B., Zhou, C., Zhang, X., & Liu, Y. (2020). A unified data-adaptive framework for high dimensional change point detection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82, 933–963.

    Article  MathSciNet  MATH  Google Scholar 

  • Page, E. S. (1955). A test for a change in a parameter occurring at an unknown point. Biometrika, 42, 523–527.

    Article  MathSciNet  MATH  Google Scholar 

  • Pesaran, M. H., & Pick, A. (2007). Econometric issues in the analysis of contagion. Journal of Economic Dynamics and Control, 31, 1245–1277.

    Article  MathSciNet  MATH  Google Scholar 

  • Wang, D., Yu, Y., & Rinaldo, A. (2021). Optimal covariance change point localization in high dimensions. Bernoulli, 27, 554–575.

    Article  MathSciNet  MATH  Google Scholar 

  • Wang, T., & Samworth, R. J. (2018). High dimensional change point estimation via sparse projection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80, 57–83.

    Article  MathSciNet  MATH  Google Scholar 

  • Wang, Z., & Zwetsloot, I. M. (2021). A change-point based control chart for detecting sparse changes in high-dimensional heteroscedastic data. arXiv preprint arXiv:2101.09424.

  • Yu, M., & Chen, X. (2017). Finite sample change point inference and identification for high-dimensional mean vectors. Preprint arXiv:1711.08747.

  • Zhang, D., & Shen, D. (2012). Multi-modal multi-task learning for joint prediction of multiple regression and classification variables in Alzheimer’s disease. NeuroImage, 59, 895–907.

    Article  Google Scholar 

  • Zhang, T., & Lavitas, L. (2018). Unsupervised self-normalized change-point testing for time series. Journal of the American Statistical Association, 113, 637–648.

    Article  MathSciNet  MATH  Google Scholar 

  • Zhou, C., Zhang, X., Zhou, W., & Liu, H., (2018). A unified framework for testing high dimensional parameters: A data-adaptive approach. Preprint arXiv:1808.02648.

Download references

Acknowledgements

The authors would like to thank the editors and the referees for their helpful comments and suggestions, which leads to an improvement of this article. We are also grateful to Dr. Solt Kovács for sharing the R codes used in Kovács et al. (2020b). This research was supported in part by the National Natural Science Foundation of China Grant 12101132 (Bin Liu), 11971116 (Zhang).

Author information

Authors and Affiliations

  1. Department of Statistics and Data Science, School of Management at Fudan University, Shanghai, 200433, China

    Xianru Wang, Bin Liu & Xinsheng Zhang

Authors
  1. Xianru Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xinsheng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bin Liu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, X., Liu, B. & Zhang, X. A computationally efficient and flexible algorithm for high dimensional mean and covariance matrix change point models. J. Korean Stat. Soc. 51, 1216–1246 (2022). https://doi.org/10.1007/s42952-022-00183-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s42952-022-00183-3

Keywords

Search

Navigation