Data-efficient quickest change detection

In the classical problem of quickest change detection, a decision maker observes a sequence of random variables. At some point of time, the distribution of the random variables changes abruptly. The objective is to detect this change in distribution with minimum possible delay, subject to a constraint on the false alarm rate. In many applications of quickest change detection, changes are rare and there is a cost associated with taking observations or acquiring data. For such applications, the classical quickest change detection model is no longer applicable. In this dissertation we extend the classical formulations by adding an additional penalty on the cost of observations used before the change point. The objective is to find a causal on-off observation control policy and a stopping time, to minimize the detection delay, subject to constraints on the false alarm rate and the cost of observations used before the change point. We show that two-threshold generalizations of the classical single-threshold tests are asymptotically optimal for the proposed formulations. The nature of optimality is strong in the sense that the false alarm rates of the two-threshold tests are at least as good as the false alarm rates of their classical counterparts. Also, the delays of the two-threshold tests are within a constant of the delays of their classical counterparts. These results indicate that an arbitrary but fixed fraction of observations can be skipped before change without any loss in asymptotic performance. A detailed performance analysis of these algorithms is provided, and guidelines are given for the design of the proposed tests, on the basis of the performance analysis. An important result obtained through this analysis is that the two constraints, on the false alarm rate and the cost of observations used before the change, can be met independent of each other. Numerical studies of these two-threshold algorithms also reveal that they have good trade-off curves, and perform significantly better than the approach of fractional sampling, where classical single threshold tests are used and the constraint on the cost of observations is met by skipping observations randomly. We first study the problem in Bayesian and minimax settings and then extend the results to more general quickest change detection models, namely, model with unknown post-change distribution, a sensor network model, and a multi-channel model.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Banerjee, Taposh

Contributors dc:contributor

• Veeravalli, Venugopal V.
• Moulin, Pierre
• Fellouris, Georgios
• Dominguez-Garcia, Alejandro

• Asymptotic Optimality
• Bayesian
• Minimax
• Generalized Likelihood Ratio Test (GLRT)
• Sensor Networks
• Multi-Channel Systems
• Quickest Change Detection
• Observation Control

Statement dc:rights

• Copyright 2014 Taposh Banerjee

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/72864

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/72864