IDEAS home Printed from https://ideas.repec.org/a/bla/jorssb/v84y2022i1p234-266.html

High‐dimensional, multiscale online changepoint detection

Author

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

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

  • 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.
    • Handle: RePEc:bla:jorssb:v:84:y:2022:i:1:p:234-266
    DOI: 10.1111/rssb.12447
    as

    Download full text from publisher

    File URL: https://doi.org/10.1111/rssb.12447
    Download Restriction: no
    File URL: https://libkey.io/10.1111/rssb.12447?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. 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.
    4. Y. Mei, 2010. "Efficient scalable schemes for monitoring a large number of data streams," Biometrika, Biometrika Trust, vol. 97(2), pages 419-433.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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. Yu Jeffrey Hu & Jeroen Rombouts & Ines Wilms, 2025. "Fast Forecasting of Unstable Data Streams for On-Demand Service Platforms," Information Systems Research, INFORMS, vol. 36(1), pages 552-571, March.
    2. Huang, Jingyan & Chan, Hock Peng, 2025. "Optimal sequential detection by sparsity likelihood," Computational Statistics & Data Analysis, Elsevier, vol. 203(C).
    3. 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.
    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, revised May 2024.
    5. 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.

    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. 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.
    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. Cho, Haeran & Kirch, Claudia, 2024. "Data segmentation algorithms: Univariate mean change and beyond," Econometrics and Statistics, Elsevier, vol. 30(C), pages 76-95.
    4. 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.
    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. Liu, Bin & Zhang, Xinsheng & Liu, Yufeng, 2022. "High dimensional change point inference: Recent developments and extensions," Journal of Multivariate Analysis, Elsevier, vol. 188(C).
    8. Andreou, Elena & Ghysels, Eric, 2006. "Monitoring disruptions in financial markets," Journal of Econometrics, Elsevier, vol. 135(1-2), pages 77-124.
    9. Aue, Alexander & Horváth, Lajos & Reimherr, Matthew L., 2009. "Delay times of sequential procedures for multiple time series regression models," Journal of Econometrics, Elsevier, vol. 149(2), pages 174-190, April.
    10. 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.
    11. Elena Andreou & Eric Ghysels, 2004. "Monitoring for Disruptions in Financial Markets," CIRANO Working Papers 2004s-26, CIRANO.
    12. Fabrizio Ghezzi & Eduardo Rossi & Lorenzo Trapani, 2024. "Fast Online Changepoint Detection," Papers 2402.04433, arXiv.org.
    13. Lajos Horváth & Zhenya Liu & Curtis Miller & Weiqing Tang, 2024. "Breaks in term structures: Evidence from the oil futures markets," International Journal of Finance & Economics, John Wiley & Sons, Ltd., vol. 29(2), pages 2317-2341, April.
    14. 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.
    15. Jana Eklund & George Kapetanios & Simon Price, 2010. "Forecasting in the presence of recent structural change," Bank of England Staff Working Paper series 406, Bank of England.
    16. Hsu, Chih-Chiang, 2007. "The MOSUM of squares test for monitoring variance changes," Finance Research Letters, Elsevier, vol. 4(4), pages 254-260, December.
    17. 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.
    18. Sven Otto & Jorg Breitung, 2020. "Backward CUSUM for Testing and Monitoring Structural Change with an Application to COVID-19 Pandemic Data," Papers 2003.02682, arXiv.org, revised Mar 2022.
    19. Carsten J. Crede, 2019. "A Structural Break Cartel Screen for Dating and Detecting Collusion," Review of Industrial Organization, Springer;The Industrial Organization Society, vol. 54(3), pages 543-574, May.
    20. 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.

    More about this item

    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:bla:jorssb:v:84:y:2022:i:1:p:234-266. 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: Wiley Content Delivery (email available below). General contact details of provider: https://edirc.repec.org/data/rssssea.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.