Data-efficient quickest change detection

Banerjee, Taposh

Permalink

https://hdl.handle.net/2142/72864 Copy

Description

Title

Data-efficient quickest change detection

Author(s)

Banerjee, Taposh

Issue Date

2015-01-21

Director of Research (if dissertation) or Advisor (if thesis)

Veeravalli, Venugopal V.

Doctoral Committee Chair(s)

Veeravalli, Venugopal V.

Committee Member(s)

• Moulin, Pierre
• Fellouris, Georgios
• Dominguez-Garcia, Alejandro

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2014-12

Permalink

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

Copyright and License Information

Copyright 2014 Taposh Banerjee

Owning Collections