IDEAS home Printed from https://ideas.repec.org/p/ehl/lserod/113665.html
   My bibliography  Save this paper

High-dimensional, multiscale online changepoint detection

Author

Listed:
  • Chen, Yudong
  • Wang, Tengyao
  • Samworth, Richard J.

Abstract

We introduce a new method for high-dimensional, online changepoint detection in settings where a p-variate Gaussian data stream may undergo a change in mean. The procedure works by performing likelihood ratio tests against simple alternatives of different scales in each coordinate, and then aggregating test statistics across scales and coordinates. The algorithm is online in the sense that both its storage requirements and worst-case computational complexity per new observation are independent of the number of previous observations; in practice, it may even be significantly faster than this. We prove that the patience, or average run length under the null, of our procedure is at least at the desired nominal level, and provide guarantees on its response delay under the alternative that depend on the sparsity of the vector of mean change. Simulations confirm the practical effectiveness of our proposal, which is implemented in the R package ocd, and we also demonstrate its utility on a seismology data set.

Suggested Citation

  • Chen, Yudong & Wang, Tengyao & Samworth, Richard J., 2022. "High-dimensional, multiscale online changepoint detection," LSE Research Online Documents on Economics 113665, London School of Economics and Political Science, LSE Library.
    • Handle: RePEc:ehl:lserod:113665
    as

    Download full text from publisher

    File URL: http://eprints.lse.ac.uk/113665/
    File Function: Open access version.
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Lajos Horváth & Gregory Rice, 2014. "Extensions of some classical methods in change point analysis," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 219-255, June.
    2. Klaus Frick & Axel Munk & Hannes Sieling, 2014. "Multiscale change point inference," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 76(3), pages 495-580, June.
    3. Rafal Baranowski & Yining Chen & Piotr Fryzlewicz, 2019. "Narrowest‐over‐threshold detection of multiple change points and change‐point‐like features," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 81(3), pages 649-672, July.
    4. Paul Fearnhead & Zhen Liu, 2007. "On‐line inference for multiple changepoint problems," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 69(4), pages 589-605, September.
    5. Tengyao Wang & Richard J. Samworth, 2018. "High dimensional change point estimation via sparse projection," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 80(1), pages 57-83, January.
    6. Y. Mei, 2010. "Efficient scalable schemes for monitoring a large number of data streams," Biometrika, Biometrika Trust, vol. 97(2), pages 419-433.
    7. Achim Zeileis & Friedrich Leisch & Christian Kleiber & Kurt Hornik, 2005. "Monitoring structural change in dynamic econometric models," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 20(1), pages 99-121, January.
    8. Leisch, Friedrich & Hornik, Kurt & Kuan, Chung-Ming, 2000. "Monitoring Structural Changes With The Generalized Fluctuation Test," Econometric Theory, Cambridge University Press, vol. 16(6), pages 835-854, December.
    9. Lajos Horváth & Gregory Rice, 2014. "Rejoinder on: Extensions of some classical methods in change point analysis," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 287-290, June.
    10. Chu, Chia-Shang James & Stinchcombe, Maxwell & White, Halbert, 1996. "Monitoring Structural Change," Econometrica, Econometric Society, vol. 64(5), pages 1045-1065, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Du, Lilun & Wen, Mengtao, 2023. "False discovery rate approach to dynamic change detection," Journal of Multivariate Analysis, Elsevier, vol. 198(C).
    2. Follain, Bertille & Wang, Tengyao & Samworth, Richard J., 2022. "High-dimensional changepoint estimation with heterogeneous missingness," LSE Research Online Documents on Economics 115014, London School of Economics and Political Science, LSE Library.
    3. Tuomas Rajala & Petteri Packalen & Mari Myllymäki & Annika Kangas, 2023. "Improving Detection of Changepoints in Short and Noisy Time Series with Local Correlations: Connecting the Events in Pixel Neighbourhoods," Journal of Agricultural, Biological and Environmental Statistics, Springer;The International Biometric Society;American Statistical Association, vol. 28(3), pages 564-590, September.
    4. Yu Jeffrey Hu & Jeroen Rombouts & Ines Wilms, 2023. "Fast Forecasting of Unstable Data Streams for On-Demand Service Platforms," Papers 2303.01887, arXiv.org.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yudong Chen & Tengyao Wang & Richard J. Samworth, 2022. "High‐dimensional, multiscale online changepoint detection," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(1), pages 234-266, February.
    2. Haeran Cho & Claudia Kirch, 2022. "Two-stage data segmentation permitting multiscale change points, heavy tails and dependence," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 74(4), pages 653-684, August.
    3. Claudia Kirch & Christina Stoehr, 2022. "Sequential change point tests based on U‐statistics," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 49(3), pages 1184-1214, September.
    4. Liu, Bin & Zhang, Xinsheng & Liu, Yufeng, 2022. "High dimensional change point inference: Recent developments and extensions," Journal of Multivariate Analysis, Elsevier, vol. 188(C).
    5. Bertille Follain & Tengyao Wang & Richard J. Samworth, 2022. "High‐dimensional changepoint estimation with heterogeneous missingness," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(3), pages 1023-1055, July.
    6. Follain, Bertille & Wang, Tengyao & Samworth, Richard J., 2022. "High-dimensional changepoint estimation with heterogeneous missingness," LSE Research Online Documents on Economics 115014, London School of Economics and Political Science, LSE Library.
    7. Elena Andreou & Eric Ghysels, 2004. "Monitoring for Disruptions in Financial Markets," CIRANO Working Papers 2004s-26, CIRANO.
    8. Fabrizio Ghezzi & Eduardo Rossi & Lorenzo Trapani, 2024. "Fast Online Changepoint Detection," Papers 2402.04433, arXiv.org.
    9. Jana Eklund & George Kapetanios & Simon Price, 2013. "Robust Forecast Methods and Monitoring during Structural Change," Manchester School, University of Manchester, vol. 81, pages 3-27, October.
    10. Eklund, Jana & Kapetanios, George & Price, Simon, 2010. "Forecasting in the presence of recent structural change," Bank of England working papers 406, Bank of England.
    11. Hsu, Chih-Chiang, 2007. "The MOSUM of squares test for monitoring variance changes," Finance Research Letters, Elsevier, vol. 4(4), pages 254-260, December.
    12. Bock, David, 2007. "Consequences of using the probability of a false alarm as the false alarm measure," Research Reports 2007:3, University of Gothenburg, Statistical Research Unit, School of Business, Economics and Law.
    13. Jan J. J. Groen & George Kapetanios & Simon Price, 2013. "Multivariate Methods For Monitoring Structural Change," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 28(2), pages 250-274, March.
    14. Ricardo C. Pedroso & Rosangela H. Loschi & Fernando Andrés Quintana, 2023. "Multipartition model for multiple change point identification," TEST: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 32(2), pages 759-783, June.
    15. Cui, Junfeng & Wang, Guanghui & Zou, Changliang & Wang, Zhaojun, 2023. "Change-point testing for parallel data sets with FDR control," Computational Statistics & Data Analysis, Elsevier, vol. 182(C).
    16. Jiang, Feiyu & Wang, Runmin & Shao, Xiaofeng, 2023. "Robust inference for change points in high dimension," Journal of Multivariate Analysis, Elsevier, vol. 193(C).
    17. Jan Verbesselt & Achim Zeileis & Martin Herold, 2011. "Near Real-Time Disturbance Detection in Terrestrial Ecosystems Using Satellite Image Time Series: Drought Detection in Somalia," Working Papers 2011-18, Faculty of Economics and Statistics, Universität Innsbruck.
    18. Anatolyev Stanislav & Kosenok Grigory, 2018. "Sequential Testing with Uniformly Distributed Size," Journal of Time Series Econometrics, De Gruyter, vol. 10(2), pages 1-22, July.
    19. Alberto Cazzola & Lucia Pasquini & Aurora Angeli, 2016. "The relationship between unemployment and fertility in Italy," Demographic Research, Max Planck Institute for Demographic Research, Rostock, Germany, vol. 34(1), pages 1-38.
    20. Otto, Sven & Breitung, Jörg, 2020. "Backward CUSUM for Testing and Monitoring Structural Change," VfS Annual Conference 2020 (Virtual Conference): Gender Economics 224533, Verein für Socialpolitik / German Economic Association.

    More about this item

    Keywords

    average run length; detection delay; high-dimensional changepoint detection; online algorithm; sequential method; grant EP/T02772X/1; EP/N031938/1; EP/P031447/1;
    All these keywords.

    JEL classification:

    • C1 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods and Methodology: General

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ehl:lserod:113665. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: LSERO Manager (email available below). General contact details of provider: https://edirc.repec.org/data/lsepsuk.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.