{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T10:06:24Z","timestamp":1760609184033,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T00:00:00Z","timestamp":1567987200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T00:00:00Z","timestamp":1567987200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"national science foundation","award":["CCF-1442635"],"award-info":[{"award-number":["CCF-1442635"]}]},{"name":"national science foundation","award":["CMMI-1538746"],"award-info":[{"award-number":["CMMI-1538746"]}]},{"name":"national science foundation","award":["CCF-1650913"],"award-info":[{"award-number":["CCF-1650913"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["EURASIP J. Adv. Signal Process."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:p>We present sequential change-point detection procedures based on linear sketches of high-dimensional signal vectors using generalized likelihood ratio (GLR) statistics. The GLR statistics allow for an unknown post-change mean that represents an anomaly or novelty. We consider both fixed and time-varying projections, derive theoretical approximations to two fundamental performance metrics: the average run length (ARL) and the expected detection delay (EDD); these approximations are shown to be highly accurate by numerical simulations. We further characterize the relative performance measure of the sketching procedure compared to that without sketching and show that there can be little performance loss when the signal strength is sufficiently large, and enough number of sketches are used. Finally, we demonstrate the good performance of sketching procedures using simulation and real-data examples on solar flare detection and failure detection in power networks.<\/jats:p>","DOI":"10.1186\/s13634-019-0635-3","type":"journal-article","created":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T13:03:50Z","timestamp":1568034230000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Sketching for sequential change-point detection"],"prefix":"10.1186","volume":"2019","author":[{"given":"Yang","family":"Cao","sequence":"first","affiliation":[]},{"given":"Andrew","family":"Thompson","sequence":"additional","affiliation":[]},{"given":"Meng","family":"Wang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6777-2951","authenticated-orcid":false,"given":"Yao","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,9]]},"reference":[{"key":"635_CR1","doi-asserted-by":"crossref","unstructured":"Y. Xie, M. Wang, A. Thompson, in Global Conference on Signal and Information Processing (GlobalSIP). Sketching for sequential change-point detection (Orlando, 2015), pp. 78\u201382.","DOI":"10.1109\/GlobalSIP.2015.7418160"},{"key":"635_CR2","doi-asserted-by":"crossref","unstructured":"A. Tartakovsky, I. Nikiforov, M. Basseville, Sequential analysis: Hypothesis Testing and Changepoint Detection (Chapman and Hall\/CRC, 2014).","DOI":"10.1201\/b17279"},{"key":"635_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511754678","volume-title":"Quickest detection","author":"HV. Poor","year":"2008","unstructured":"HV. Poor, O. Hadjiliadis, Quickest detection (Cambridge University Press, Cambridge, 2008)."},{"key":"635_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000060","volume":"10","author":"D. P. Woodruff","year":"2014","unstructured":"D. P. Woodruff, Sketching as a tool for numerical linear algebra. Found. Trends. Theor. Comput. Sci.10:, 1\u2013157 (2014).","journal-title":"Found. Trends. Theor. Comput. Sci."},{"key":"635_CR5","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1109\/Allerton.2012.6483331","volume-title":"Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on","author":"G. Dasarathy","year":"2012","unstructured":"G. Dasarathy, P. Shah, B. N. Bhaskar, R. Nowak, in Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on. Covariance sketching (IEEEMonticello, 2012), pp. 1026\u20131033."},{"key":"635_CR6","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1109\/EUSIPCO.2016.7760261","volume-title":"Signal Processing Conference (EUSIPCO), 2016 24th European","author":"Y. Chi","year":"2016","unstructured":"Y. Chi, in Signal Processing Conference (EUSIPCO), 2016 24th European. Kronecker covariance sketching for spatial-temporal data (IEEEBudapest, 2016), pp. 316\u2013320."},{"key":"635_CR7","unstructured":"Y. Wang, H. -Y. Tung, A. J. Smola, A. Anandkumar, in Advances in Neural Information Processing Systems. Fast and guaranteed tensor decomposition via sketching (Montreal, 2015), pp. 991\u2013999."},{"key":"635_CR8","unstructured":"A. Alaoui, M. W. Mahoney, in Advances in Neural Information Processing Systems. Fast randomized kernel ridge regression with statistical guarantees (Montreal, 2015), pp. 775\u2013783."},{"key":"635_CR9","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-642-03784-9_34","volume-title":"International Symposium on String Processing and Information Retrieval","author":"Y. Bachrach","year":"2009","unstructured":"Y. Bachrach, R. Herbrich, E. Porat, in International Symposium on String Processing and Information Retrieval. Sketching algorithms for approximating rank correlations in collaborative filtering systems (SpringerNew York, 2009), pp. 344\u2013352."},{"key":"635_CR10","unstructured":"G. Raskutti, M. Mahoney, in International Conference on Machine Learning. Statistical and algorithmic perspectives on randomized sketching for ordinary least-squares (Lille, 2015), pp. 617\u2013625."},{"key":"635_CR11","unstructured":"P. Indyk, in Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms Society for Industrial and Applied Mathematics. Explicit constructions for compressed sensing of sparse signals (San Francisco, 2008), pp. 30\u201333."},{"issue":"2A","key":"635_CR12","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1214\/10-AOAS400","volume":"5","author":"D. Siegmund","year":"2011","unstructured":"D. Siegmund, B. Yakir, N. R. Zhang, Detecting simultaneous variant intervals in aligned sequences. Ann. Appl. Stat.5(2A), 645\u2013668 (2011).","journal-title":"Ann. Appl. Stat."},{"issue":"2","key":"635_CR13","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/LSP.2014.2352116","volume":"22","author":"G. K. Atia","year":"2015","unstructured":"G. K. Atia, Change detection with compressive measurements. Sig. Process. Lett. IEEE.22(2), 182\u2013186 (2015).","journal-title":"Sig. Process. Lett. IEEE."},{"issue":"1","key":"635_CR14","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1214\/aos\/1176324466","volume":"23","author":"D. Siegmund","year":"1995","unstructured":"D. Siegmund, E. S. Venkatraman, Using the generalized likelihood ratio statistic for sequential detection of a change-point. Ann. Stat.23(1), 255\u2013271 (1995).","journal-title":"Ann. Stat."},{"issue":"2","key":"635_CR15","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1214\/13-AOS1094","volume":"41","author":"Y. Xie","year":"2013","unstructured":"Y. Xie, D. Siegmund, Sequential multi-sensor change-point detection. Ann. Stat.41(2), 670\u2013692 (2013).","journal-title":"Ann. Stat."},{"issue":"3","key":"635_CR16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1080\/00224065.1996.11979681","volume":"28","author":"G. C. Runger","year":"1996","unstructured":"G. C. Runger, Projections and the U-squared multivariate control chart. J. Qual. Technol.28(3), 313\u2013319 (1996).","journal-title":"J. Qual. Technol."},{"key":"635_CR17","first-page":"75","volume":"89","author":"O. Bodnar","year":"2005","unstructured":"O. Bodnar, W. Schmid, Multivariate control charts based on a projection approach. Allg. Stat. Arch.89:, 75\u201393 (2005).","journal-title":"Allg. Stat. Arch."},{"issue":"2","key":"635_CR18","doi-asserted-by":"publisher","first-page":"447","DOI":"10.2478\/amcs-2013-0034","volume":"23","author":"E. Skuba\u0142lska-Rafajlowicz","year":"2013","unstructured":"E. Skuba\u0142lska-Rafajlowicz, Random projections and Hotelling\u2019s T2 statistics for change detection in high-dimensional data analysis. Int. J. Appl. Math. Comput. Sci.23(2), 447\u2013461 (2013).","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"635_CR19","volume-title":"Stochastic models, statistics and their applications","author":"E. Skuba\u0142ska-Rafajlowicz","year":"2015","unstructured":"E. Skuba\u0142ska-Rafajlowicz, in Stochastic models, statistics and their applications, 122. Change-point detection of the mean vector with fewer observations than the dimension using instanenous normal random projections (Springer Proc. Math. StatNew York, 2015)."},{"key":"635_CR20","unstructured":"D. C. Montgomery, Introduction to statistical quality control (Wiley, 2008)."},{"issue":"2","key":"635_CR21","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1109\/JSTSP.2009.2039178","volume":"4","author":"M. A. Davenport","year":"2010","unstructured":"M. A. Davenport, P. T. Boufounos, M. B. Wakin, R. G. Baraniuk, Signal processing with compressive measurements. Sel. Top. Sig. Process. IEEE. J.4(2), 445\u2013460 (2010).","journal-title":"Sel. Top. Sig. Process. IEEE. J."},{"key":"635_CR22","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1214\/12-EJS686","volume":"6","author":"E. Arias-Castro","year":"2012","unstructured":"E. Arias-Castro, et al., Detecting a vector based on linear measurements. Electron. J. Stat.6:, 547\u2013558 (2012).","journal-title":"Electron. J. Stat."},{"key":"635_CR23","unstructured":"J. Geng, W. Xu, L. Lai, in Information Theory (ISIT), 2013 IEEE International Symposium on, Istanbul, Turkey. Quickest search over multiple sequences with mixed observations, (2013), pp. 2582\u20132586."},{"key":"635_CR24","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1109\/Allerton.2013.6736697","volume-title":"Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on","author":"W. Xu","year":"2013","unstructured":"W. Xu, L. Lai, in Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on. Compressed hypothesis testing: to mix or not to mix? (IEEEMonticello, 2013), pp. 1443\u20131449."},{"key":"635_CR25","unstructured":"Z. Harchaoui, E. Moulines, F. R. Bach, in Advances in Neural Information Processing Systems. Kernel change-point analysis (Vancouver, 2009), pp. 609\u2013616."},{"key":"635_CR26","unstructured":"S. Arlot, A. Celisse, Z. Harchaoui, Kernel change-point detection (2012). arXiv preprint arXiv:1202.3878."},{"issue":"1","key":"635_CR27","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1109\/TPWRS.2015.2394246","volume":"31","author":"Y. C. Chen","year":"2016","unstructured":"Y. C. Chen, T. Banerjee, A. D. Dom\u00ednguez-Garc\u00eda, V. V. Veeravalli, Quickest line outage detection and identification. Power. Syst. IEEE. Trans.31(1), 749\u2013758 (2016).","journal-title":"Power. Syst. IEEE. Trans."},{"key":"635_CR28","first-page":"1","volume-title":"High Performance Extreme Computing Conference (HPEC), 2014 IEEE","author":"D. Mishin","year":"2014","unstructured":"D. Mishin, K. Brantner-Magee, F. Czako, A. S. Szalay, in High Performance Extreme Computing Conference (HPEC), 2014 IEEE. Real time change point detection by incremental PCA in large scale sensor data (IEEEWaltham, 2014), pp. 1\u20136."},{"key":"635_CR29","volume-title":"Frontier in Statistical Quality Control, pp. 19\u201335","author":"F. Tsung","year":"2010","unstructured":"F. Tsung, K. Wang, in Frontier in Statistical Quality Control, pp. 19\u201335. Adaptive charting techniques: literature review and extensions (Springer-VerlagNew York, 2010)."},{"key":"635_CR30","unstructured":"J. Chen, S. -H. Kim, Y. Xie, S3T: an efficient score-statistic for spatio-temporal surveillance (2017). arXiv:1706.05331."},{"key":"635_CR31","doi-asserted-by":"crossref","unstructured":"W. Xu, B. Hassibi, in Info. Theory Workshop. Efficient compressive sensing with deterministic guarantees using expander graphs, (2007).","DOI":"10.1109\/ITW.2007.4313110"},{"key":"635_CR32","doi-asserted-by":"publisher","first-page":"2336","DOI":"10.1109\/ISIT.2015.7282873","volume-title":"Information Theory (ISIT), 2015 IEEE International Symposium on, Hong Kong","author":"Y. Chen","year":"2015","unstructured":"Y. Chen, C. Suh, AJ Goldsmith, in Information Theory (ISIT), 2015 IEEE International Symposium on, Hong Kong. Information recovery from pairwise measurements: a Shannon-theoretic approach (IEEEHong Kong, 2015), pp. 2336\u20132340."},{"key":"635_CR33","unstructured":"A. K Massimino, M. A. Davenport, in Proc. Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS). One-bit matrix completion for pairwise comparison matrices (Lausanne, 2013)."},{"key":"635_CR34","doi-asserted-by":"publisher","DOI":"10.1002\/0471725331","volume-title":"A user\u2019s guide to principle components","author":"J. E. Jackson","year":"1991","unstructured":"J. E. Jackson, A user\u2019s guide to principle components (Wiley, New York, 1991)."},{"issue":"5","key":"635_CR35","doi-asserted-by":"publisher","first-page":"1279","DOI":"10.1007\/s10208-014-9227-7","volume":"15","author":"L. Balzano","year":"2015","unstructured":"L. Balzano, S. J. Wright, Local convergence of an algorithm for subspace identification from partial data. Found. Comput. Math.15(5), 1279\u20131314 (2015).","journal-title":"Found. Comput. Math."},{"key":"635_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1862-1","volume-title":"Sequential Analysis: Test and Confidence Intervals","author":"D. Siegmund","year":"1985","unstructured":"D. Siegmund, Sequential Analysis: Test and Confidence Intervals (Springer, New York, 1985)."},{"key":"635_CR37","volume-title":"The statistics of gene mapping","author":"D. Siegmund","year":"2007","unstructured":"D. Siegmund, B. Yakir, The statistics of gene mapping (Springer, New York, 2007)."},{"issue":"1","key":"635_CR38","doi-asserted-by":"publisher","first-page":"84","DOI":"10.2307\/3213377","volume":"16","author":"H. Ruben","year":"1979","unstructured":"H. Ruben, The volume of an isotropic random parallelotope. J. Appl. Probab.16(1), 84\u201394 (1979).","journal-title":"J. Appl. Probab."},{"issue":"3","key":"635_CR39","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF00049302","volume":"42","author":"P. Frankl","year":"1990","unstructured":"P. Frankl, H. Maehara, Some geometric applications of the beta distribution. Ann. Inst. Statist. Math.42(3), 463\u2013474 (1990).","journal-title":"Ann. Inst. Statist. Math."},{"issue":"2","key":"635_CR40","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1109\/18.910588","volume":"47","author":"D. Burshtein","year":"2001","unstructured":"D. Burshtein, G. Miller, Expander graph arguments for message-passing algorithms. IEEE Trans. Inf. Theory.47(2), 782 \u2013790 (2001).","journal-title":"IEEE Trans. Inf. Theory."},{"key":"635_CR41","first-page":"589","volume":"342","author":"E. J. Candes","year":"2008","unstructured":"E. J. Candes, The restricted isometry property and its implications for compressed sensing. Compte Rendus de l\u2019Academie des Sciences, Paris, Serie I. 342:, 589\u2013592 (2008).","journal-title":"Compte Rendus de l\u2019Academie des Sciences, Paris, Serie I"},{"issue":"3","key":"635_CR42","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1080\/00401706.1985.10488053","volume":"27","author":"W. H. Woodall","year":"1985","unstructured":"W. H. Woodall, M. M. Ncube, Multivariate CUSUM quality-control procedures. Technometrics. 27(3), 285\u2013292 (1985).","journal-title":"Technometrics"},{"issue":"1","key":"635_CR43","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/JSTSP.2012.2234082","volume":"7","author":"Y. Xie","year":"2013","unstructured":"Y. Xie, J. Huang, R. Willett, Change-point detection for high-dimensional time series with missing data. Sel. Top. Sig. Process. IEEE. J.7(1), 12\u201327 (2013).","journal-title":"Sel. Top. Sig. Process. IEEE. J."},{"issue":"6684","key":"635_CR44","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D. J. Watts","year":"1998","unstructured":"D. J. Watts, S. H. Strogatz, Collective dynamics of \u2018small-world\u2019 networks. Nature. 393(6684), 440\u2013442 (1998).","journal-title":"Nature"},{"key":"635_CR45","doi-asserted-by":"crossref","unstructured":"A. Abur, A. G. Exposito, Power system state estimation: Theory and Implementation (CRC Press, 2004).","DOI":"10.1201\/9780203913673"},{"issue":"1","key":"635_CR46","doi-asserted-by":"publisher","first-page":"C1","DOI":"10.1016\/j.jeconom.2018.04.002","volume":"19","author":"J. Fan","year":"2016","unstructured":"J. Fan, Y. Liao, H. Liu, An overview on the estimation of large covariance and precision matrices. Econ. J.19(1), C1\u2013C32 (2016).","journal-title":"Econ. J."},{"key":"635_CR47","unstructured":"M. Kapralov, V. K. Potluru, D. P. Woodruff, in International Conference on Machine Learning. How to fake multiply by a Gaussian matrix (New York, 2016)."},{"key":"635_CR48","volume-title":"A handbook of mathematical functions, with formulas, graphs and mathematical tables","author":"M. Abramowitz","year":"1964","unstructured":"M. Abramowitz, I. Stegun, A handbook of mathematical functions, with formulas, graphs and mathematical tables, 10th (Dover, New York, 1964)."},{"key":"635_CR49","unstructured":"A. Thompson, Quantitative analysis of algorithms for compressed signal recovery. PhD thesis, School of Mathematics, University of Edinburgh (2012)."},{"issue":"5","key":"635_CR50","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1214\/aos\/1015957395","volume":"28","author":"B. Laurent","year":"2000","unstructured":"B. Laurent, P. Massart, Adaptive estimation of a quadratic functional by model selection. Ann. Stat.28(5), 1302\u20131338 (2000).","journal-title":"Ann. Stat."}],"container-title":["EURASIP Journal on Advances in Signal Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13634-019-0635-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13634-019-0635-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13634-019-0635-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T23:06:56Z","timestamp":1599520016000},"score":1,"resource":{"primary":{"URL":"https:\/\/asp-eurasipjournals.springeropen.com\/articles\/10.1186\/s13634-019-0635-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,9]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["635"],"URL":"https:\/\/doi.org\/10.1186\/s13634-019-0635-3","relation":{},"ISSN":["1687-6180"],"issn-type":[{"type":"electronic","value":"1687-6180"}],"subject":[],"published":{"date-parts":[[2019,9,9]]},"assertion":[{"value":"21 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"42"}}