TY - JOUR

T1 - Data-Efficient Quickest Change Detection with On-Off Observation Control

AU - Banerjee, Taposh

AU - Veeravalli, Venugopal V.

N1 - Funding Information:
We thank the Associate Editor and the referees for their constructive suggestions and comments. We would also like to thank Dr. K. Premkumar for useful discussions. This research was partially supported by the National Science Foundation under grant CCF 08-30169, through the University of Illinois at Urbana–Champaign. This research was also supported in part by the U.S. Army Research Office MURI grant W911NF-06-1-0094, through a subcontract from Brown University at the University of Illinois, and by the U.S. Defense Threat Reduction Agency through subcontract 147755 at the University of Illinois from prime award HDTRA1-10-1-0086.

PY - 2012/1

Y1 - 2012/1

N2 - In this article we extend Shiryaev's quickest change detection formulation by also accounting for the cost of observations used before the change point. The observation cost is captured through the average number of observations used in the detection process before the change occurs. The objective is to select an on-off observation control policy that decides whether or not to take a given observation, along with the stopping time at which the change is declared, to minimize the average detection delay, subject to constraints on both the probability of false alarm and the observation cost. By considering a Lagrangian relaxation of the constraint problem and using dynamic programming arguments, we obtain an a posteriori probability-based two-threshold algorithm that is a generalized version of the classical Shiryaev algorithm. We provide an asymptotic analysis of the two-threshold algorithm and show that the algorithm is asymptotically optimal-that is, the performance of the two-threshold algorithm approaches that of the Shiryaev algorithm-for a fixed observation cost, as the probability of false alarm goes to zero. We also show, using simulations, that the two-threshold algorithm has good observation cost-delay trade-off curves and provides significant reduction in observation cost compared to the naïve approach of fractional sampling, where samples are skipped randomly. Our analysis reveals that, for practical choices of constraints, the two thresholds can be set independent of each other: one based on the constraint of false alarm and another based on the observation cost constraint alone.

AB - In this article we extend Shiryaev's quickest change detection formulation by also accounting for the cost of observations used before the change point. The observation cost is captured through the average number of observations used in the detection process before the change occurs. The objective is to select an on-off observation control policy that decides whether or not to take a given observation, along with the stopping time at which the change is declared, to minimize the average detection delay, subject to constraints on both the probability of false alarm and the observation cost. By considering a Lagrangian relaxation of the constraint problem and using dynamic programming arguments, we obtain an a posteriori probability-based two-threshold algorithm that is a generalized version of the classical Shiryaev algorithm. We provide an asymptotic analysis of the two-threshold algorithm and show that the algorithm is asymptotically optimal-that is, the performance of the two-threshold algorithm approaches that of the Shiryaev algorithm-for a fixed observation cost, as the probability of false alarm goes to zero. We also show, using simulations, that the two-threshold algorithm has good observation cost-delay trade-off curves and provides significant reduction in observation cost compared to the naïve approach of fractional sampling, where samples are skipped randomly. Our analysis reveals that, for practical choices of constraints, the two thresholds can be set independent of each other: one based on the constraint of false alarm and another based on the observation cost constraint alone.

KW - Asymptotic optimality

KW - Nonlinear renewal theory

KW - Observation control

KW - Quickest change detection

UR - http://www.scopus.com/inward/record.url?scp=84858166057&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858166057&partnerID=8YFLogxK

U2 - 10.1080/07474946.2012.651981

DO - 10.1080/07474946.2012.651981

M3 - Article

AN - SCOPUS:84858166057

SN - 0747-4946

VL - 31

SP - 40

EP - 77

JO - Sequential Analysis

JF - Sequential Analysis

IS - 1

ER -