Abstract

Sequential/Online change point detection involves continuously monitoring time

series data and triggering an alarm when shifts in the data distribution are detected. We

propose an algorithm for real-time identification of alterations in the transition matrices of

high-dimensional vector auto-regressive models. This algorithm initially estimates transition

matrices and error term variances using regularization techniques applied to training data,

then computes a specific test statistic to detect changes in transition matrices as new data

batches arrive. We establish the asymptotic normality of the test statistic under the scenario

of no change points, subject to mild conditions. An alarm is raised when the calculated test

statistic exceeds a predefined quantile of the standard normal distribution. We demonstrate

that as the size of the change (jump size) increases, the test’s power approaches one. Empirical

validation of the algorithm’s effectiveness is conducted across various simulation scenarios.

Finally, we discuss two applications of the proposed methodology: analyzing shocks within

S&P 500 data and detecting the timing of seizures in EEG data.

Information

Preprint No.SS-2024-0182
Manuscript IDSS-2024-0182
Complete AuthorsYuhan Tian, Abolfazl Safikhani
Corresponding AuthorsAbolfazl Safikhani
Emailsasafikha@gmu.edu

References

  1. Adams, R. P. and D. J. MacKay (2007). Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742.
  2. Aminikhanghahi, S. and D. J. Cook (2017). A survey of methods for time series change point detection. Knowledge and information systems 51(2), 339–367.
  3. Aminikhanghahi, S., T. Wang, and D. J. Cook (2018). Real-time change point detection with application to smart home time series data. IEEE Transactions on Knowledge and Data Engineering 31(5), 1010–1023.
  4. Bai, P., A. Safikhani, and G. Michailidis (2023). Multiple change point detection in reduced rank high dimensional vector autoregressive models. Journal of the American Statistical Association 118(544), 2776–2792.
  5. Bardwell, L., P. Fearnhead, I. A. Eckley, S. Smith, and M. Spott (2019). Most recent changepoint detection in panel data. Technometrics 61(1), 88–98.
  6. Basu, S., X. Li, and G. Michailidis (2019). Low rank and structured modeling of high-dimensional vector autoregressions. IEEE Transactions on Signal Processing 67(5), 1207–1222.
  7. Basu, S. and G. Michailidis (2015). Regularized estimation in sparse high-dimensional time series models. The Annals of Statistics 43(4), 1535–1567.
  8. Cabrieto, J., F. Tuerlinckx, P. Kuppens, M. Grassmann, and E. Ceulemans (2017). Detecting correlation changes in multivariate time series: A comparison of four non-parametric change point detection methods. Behavior research methods 49, 988–1005.
  9. Chan, H. P. (2017, December).
  10. Optimal sequential detection in multi-stream data. The Annals of Statistics 45(6), 2736–2763.
  11. Chan, N. H., C. Y. Yau, and R.-M. Zhang (2014). Group lasso for structural break time series. Journal of the American Statistical Association 109(506), 590–599.
  12. Chen, H. (2019). Sequential change-point detection based on nearest neighbors. The Annals of Statistics 47(3), 1381–1407.
  13. Chen, H. and L. Chu (2019). gStream: Graph-Based Sequential Change-Point Detection for Streaming Data. R package version 0.2.0.
  14. Chen, Y., T. Wang, and R. J. Samworth (2022). High-dimensional, multiscale online changepoint detection. Journal of the Royal Statistical Society Series B: Statistical Methodology 84(1), 234–266.
  15. Choi, S. W., E. B. Martin, A. J. Morris, and I.-B. Lee (2006). Adaptive multivariate statistical process control for monitoring time-varying processes. Industrial & engineering chemistry research 45(9), 3108–3118.
  16. Chu, L. and H. Chen (2022). Sequential change-point detection for high-dimensional and non-euclidean data. IEEE Transactions on Signal Processing 70, 4498–4511.
  17. De Ketelaere, B., M. Hubert, and E. Schmitt (2015). Overview of pca-based statistical process-monitoring methods for time-dependent, high-dimensional data. Journal of Quality Technology 47(4), 318–335.
  18. Deshpande, Y., A. Javanmard, and M. Mehrabi (2023). Online debiasing for adaptively collected highdimensional data with applications to time series analysis. Journal of the American Statistical Association 118(542), 1126–1139.
  19. Dette, H. and J. G¨osmann (2020). A likelihood ratio approach to sequential change point detection for a general class of parameters. Journal of the American Statistical Association 115(531), 1361–1377.
  20. Goebel, R., A. Roebroeck, D.-S. Kim, and E. Formisano (2003). Investigating directed cortical interactions in time-resolved fmri data using vector autoregressive modeling and granger causality mapping. Magnetic resonance imaging 21(10), 1251–1261.
  21. G¨osmann, J., C. Stoehr, J. Heiny, and H. Dette (2022). Sequential change point detection in high dimensional time series. Electronic Journal of Statistics 16(1), 3608–3671.
  22. Hawkins, D. M. and K. Zamba (2005). Statistical process control for shifts in mean or variance using a changepoint formulation. Technometrics 47(2), 164–173.
  23. He, X. B. and Y. P. Yang (2008). Variable mwpca for adaptive process monitoring. Industrial & Engineering Chemistry Research 47(2), 419–427.
  24. Jandhyala, V., S. Fotopoulos, I. MacNeill, and P. Liu (2013). Inference for single and multiple change-points in time series. Journal of Time Series Analysis 34(4), 423–446.
  25. Keshavarz, H., G. Michailidis, and Y. Atchad´e (2020). Sequential change-point detection in high-dimensional gaussian graphical models. The Journal of Machine Learning Research 21(1), 3125–3181.
  26. Ku, W., R. H. Storer, and C. Georgakis (1995). Disturbance detection and isolation by dynamic principal component analysis. Chemometrics and intelligent laboratory systems 30(1), 179–196.
  27. Loh, P.-L. and M. J. Wainwright (2012). High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity. The Annals of Statistics 40(3), 1637–1664.
  28. L¨utkepohl, H. (2005). New introduction to multiple time series analysis. Springer Science & Business Media.
  29. Mei, Y. (2010). Efficient scalable schemes for monitoring a large number of data streams. Biometrika 97(2), 419–433.
  30. Montgomery, D. C. (2019). Introduction to statistical quality control. John wiley & sons.
  31. Page, E. S. (1954). Continuous inspection schemes. Biometrika 41(1/2), 100–115.
  32. Pagotto, A. (2019). ocp: Bayesian Online Changepoint Detection. R package version 0.1.1.
  33. Pan, X. and J. E. Jarrett (2012). Why and how to use vector autoregressive models for quality control: the guideline and procedures. Quality & Quantity 46(3), 935–948.
  34. Qiu, P. (2013). Introduction to statistical process control. CRC press.
  35. Qiu, P. and X. Xie (2022). Transparent sequential learning for statistical process control of serially correlated data. Technometrics 64(4), 487–501.
  36. Roberts, S. (2000). Control chart tests based on geometric moving averages. Technometrics 42(1), 97–101.
  37. Rosser Jr, J. B. and R. G. Sheehan (1995). A vector autoregressive model of the saudi arabian economy. Journal of Economics and Business 47(1), 79–90.
  38. Routtenberg, T. and Y. Xie (2017). Pmu-based online change-point detection of imbalance in three-phase power systems. In 2017 IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT), pp. 1–5. IEEE.
  39. Safikhani, A., Y. Bai, and G. Michailidis (2022). Fast and scalable algorithm for detection of structural breaks in big var models. Journal of Computational and Graphical Statistics 31(1), 176–189.
  40. Safikhani, A. and A. Shojaie (2022). Joint structural break detection and parameter estimation in highdimensional nonstationary var models. Journal of the American Statistical Association 117(537), 251–264.
  41. Shewhart, W. A. (1930). Economic quality control of manufactured product 1. Bell System Technical Journal 9(2), 364–389.
  42. Vazzoler, S. (2021). sparsevar: Sparse VAR/VECM Models Estimation. R package version 0.1.0.
  43. Wang, D., Y. Yu, A. Rinaldo, and R. Willett (2019). Localizing changes in high-dimensional vector autoregressive processes. arXiv preprint arXiv:1909.06359.
  44. Wong, K. C., Z. Li, and A. Tewari (2020). Lasso guarantees for β-mixing heavy-tailed time series. The Annals of Statistics 48(2), 1124–1142.
  45. Xie, Y. and D. Siegmund (2013). Sequential multi-sensor change-point detection. In 2013 Information Theory and Applications Workshop (ITA), pp. 1–20. IEEE.
  46. Xu, Q., Y. Mei, and G. V. Moustakides (2021). Optimum multi-stream sequential change-point detection with sampling control. IEEE Transactions on Information Theory 67(11), 7627–7636.
  47. Zhang, C., N. Chen, and J. Wu (2020). Spatial rank-based high-dimensional monitoring through random projection. Journal of Quality Technology 52(2), 111–127.
  48. Zhang, J., Z. Wei, Z. Yan, M. Zhou, and A. Pani (2017). Online change-point detection in sparse time series with application to online advertising. IEEE Transactions on Systems, Man, and Cybernetics: Systems 49(6), 1141–1151.
  49. Zhang, M., L. Xie, and Y. Xie (2023). Spectral cusum for online network structure change detection. IEEE Transactions on Information Theory 69(7), 4691–4707.

Acknowledgments

The authors have no acknowledgments to declare.

Supplementary Materials

The online supplementary material includes proofs of lemmas and theorems, along

with additional simulation and real data experiments.

Supplementary materials are available for download.