Change detection via affine and quadratic detectors. (English) Zbl 1390.62169

The goal of the paper is to develop a specific application of the convex optimization based hypothesis testing techniques developed in [the second and the last author, Electron. J. Stat. 10, No. 2, 2204–2242 (2016; Zbl 1345.62077)]. The authors present a computational framework to solve change-point detection problems which is completely general: it can process many high-dimensional situations achieving improved false detection control. Change-point detection can be viewed as a multiple-testing problem. The proposed optimization framework is computationally efficient. Moreover, with use of this framework, we can control false detection uniformly according to a pre-specified level. Assuming the observation noises are zero mean sub-Gaussian, the authors develop sequential decision rules and demonstrate that these rules are near-optimal in this context.


62M07 Non-Markovian processes: hypothesis testing
62G10 Nonparametric hypothesis testing
62J15 Paired and multiple comparisons; multiple testing
62C20 Minimax procedures in statistical decision theory
90C22 Semidefinite programming


Zbl 1345.62077
Full Text: DOI arXiv Euclid


[1] M. Basseville and I. Nikiforov., Detection of Abrupt Changes: Theory and Application. Prentice-Hall, Englewood Cliffs, N.J., 1993. · Zbl 1407.62012
[2] E. Brodsky and B. S. Darkhovsky., Nonparametric methods in change point problems, volume 243. Springer Science & Business Media, 2013. · Zbl 1319.62168
[3] Y. Cao, S. Zhu, Y. Xie, J. Key, J. Kacher, R. R. Unocic, and C. M. Rouleau. Sequential adaptive detection for in-situ transmission electron microscopy (tem)., arXiv preprint arXiv:1710.11297, 2017.
[4] J. Chen and A. Gupta., Parametric statistical change point analysis: with applications to genetics, medicine, and finance. Boston: Birkhäuser, 2012. · Zbl 1273.62016
[5] F. Enikeeva and Z. Harchaoui. High-dimensional change-point detection with sparse alternatives., arXiv preprint arXiv:1312.1900, 2013. · Zbl 1427.62036
[6] G. Fellouris and G. Sokolov. Second-order asymptotic optimality in multisensor sequential change detection., IEEE Transactions on Information Theory, 62(6) :3662-3675, 2016. · Zbl 1359.94221
[7] N. H. Gholson and R. L. Moose. Maneuvering target tracking using adaptive state estimation., IEEE Transactions on Aerospace and Electronic Systems, 13(3):310-317, 1977.
[8] A. Goldenshluger, A. Juditsky, and A. Nemirovski. Hypothesis testing by convex optimization., Electronic Journal of Statistics, 9(2) :1645-1712, 2015. · Zbl 1327.62287
[9] A. Goldenshluger, A. Juditsky, A. Tsybakov, and A. Zeevi. Change-point estimation from indirect observations. 1. minimax complexity., Ann. Inst. Henri Poincare Probab. Stat., 44:787-818, 2008. · Zbl 1206.62048
[10] A. Goldenshluger, A. Juditsky, A. Tsybakov, and A. Zeevi. Change-point estimation from indirect observations. 2. adaptation., Ann. Inst. H. Poincare Probab. Statist, 44(5):819-836, 2008. · Zbl 1206.62047
[11] L. Gordon and M. Pollak. An efficient sequential nonparametric scheme for detecting a change of distribution., The Annals of Statistics, pages 763-804, 1994. · Zbl 0816.62066
[12] V. Guigues. Nonparametric multidimensional breakpoint detection for the mean and correlations of a discrete time stochastic process., Journal of Nonparametric Statistics, 24:857-882, 2012. · Zbl 1254.62093
[13] Y. I. Ingster, C. Pouet, and A. B. Tsybakov. Classification of sparse high-dimensional vectors., Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 367 (1906):4427-4448, 2009. · Zbl 1185.62115
[14] Y. I. Ingster and I. A. Suslina. On detection of a signal of known shape in multi-channel system., Zapiski Nauchnykh Seminarov POMI, 294:88-112, 2002. · Zbl 1259.94029
[15] Y. I. Ingster, A. B. Tsybakov, and N. Verzelen. Detection boundary in sparse regression., Electron. J. Statist., 4 :1476-1526, 2010. · Zbl 1329.62314
[16] A. Juditski and A. Nemirovski. On sequential hypotheses testing via convex optimization., Automation and Remote Control, 76:809-825, 2015. · Zbl 1323.62081
[17] A. Juditsky and A. Nemirovski. Hypothesis testing via affine detectors., Electronic Journal of Statistics, 10 :2204-2242, 2016. · Zbl 1345.62077
[18] A. Korostelev and O. Lepski. On a multi-channel change-point problem., Mathematical Methods of Statistics, 17(3):187-197, 2008. · Zbl 1231.62151
[19] T. L. Lai. Sequential changepoint detection in quality control and dynamical systems., Journal of the Royal Statistical Society. Series B (Methodological), pages 613-658, 1995. · Zbl 0832.62072
[20] T. L. Lai. Information bounds and quick detection of parameter changes in stochastic systems., IEEE Transactions on Information Theory, 44(7) :2917-2929, 1998. · Zbl 0955.62084
[21] A. Lakhina, M. Crovella, and C. Diot. Diagnosing network-wide traffic anomalies. In, ACM SIGCOMM Computer Communication Review, volume 34, pages 219-230. ACM, 2004.
[22] C. Lévy-Leduc and F. Roueff. Detection and localization of change-points in high-dimensional network traffic data., The Annals of Applied Statistics, pages 637-662, 2009. · Zbl 1166.62094
[23] K. Liu, R. Zhang, and Y. Mei. Scalable sum-shrinkage schemes for distributed monitoring large-scale data streams., arXiv preprint arXiv:1603.08652, 2016. · Zbl 1412.62070
[24] G. Lorden. Procedures for reacting to a change in distribution., The Annals of Mathematical Statistics, pages 1897-1908, 1971. · Zbl 0255.62067
[25] E. Mazor, A. Averbuch, Y. Bar-Shalom, and J. Dayan. Interacting multiple model methods in target tracking: a survey., IEEE Transactions on Aerospace and Electronic Systems, 34(1):103-123, 1998.
[26] Y. Mei. Asymptotic optimality theory for decentralized sequential hypothesis testing in sensor networks., IEEE Transactions on Information Theory, 54(5) :2072-2089, 2008. · Zbl 1332.94026
[27] G. V. Moustakides. Optimal stopping times for detecting changes in distributions., The Annals of Statistics, pages 1379-1387, 1986. · Zbl 0612.62116
[28] M. H. Neumann. Optimal change-point estimation in inverse problems., Scandinavian Journal of Statistics, 24(4):503-521, 1997. · Zbl 0902.62048
[29] E. Page. Continuous inspection schemes., Biometrika, 41(1/2):100-115, 1954. · Zbl 0056.38002
[30] M. Pollak. Optimal detection of a change in distribution., The Annals of Statistics, pages 206-227, 1985. · Zbl 0573.62074
[31] M. Pollak. Average run lengths of an optimal method of detecting a change in distribution., The Annals of Statistics, pages 749-779, 1987. · Zbl 0632.62080
[32] H. V. Poor and O. Hadjiliadis., Quickest detection, volume 40. Cambridge University Press Cambridge, 2009. · Zbl 1271.62015
[33] W. A. Shewhart., Economic control of quality of manufactured product. ASQ Quality Press, 1931.
[34] A. N. Shiryaev. On optimum methods in quickest detection problems., Theory of Probability & Its Applications, 8(1):22-46, 1963. · Zbl 0213.43804
[35] D. Siegmund., Sequential Analysis: Tests and Confidence Intervals. Springer Science & Business Media, 1985. · Zbl 0573.62071
[36] D. Siegmund and B. Yakir., The statistics of gene mapping. Springer Science & Business Media, 2007. · Zbl 1280.62012
[37] A. Tartakovsky, I. Nikiforov, and M. Basseville., Sequential analysis: Hypothesis testing and changepoint detection. CRC Press, 2014. · Zbl 1341.62026
[38] A. G. Tartakovsky and V. V. Veeravalli. Change-point detection in multichannel and distributed systems., Applied Sequential Methodologies: Real-World Examples with Data Analysis, 173:339-370, 2004. · Zbl 1082.62068
[39] A. G. Tartakovsky and V. V. Veeravalli. Asymptotically optimal quickest change detection in distributed sensor systems., Sequential Analysis, 27(4):441-475, 2008. · Zbl 1247.93014
[40] V. V. Veeravalli and T. Banerjee. Quickest change detection., Academic press library in signal processing: Array and statistical signal processing, 3:209-256, 2013.
[41] A. S. Willsky., Detection of abrupt changes in dynamic systems. Springer, 1985.
[42] Y. Xie and D. Siegmund. Sequential multi-sensor change-point detection., Annals of Statistics, 41(2):670-692, 2013. · Zbl 1267.62084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.