Logo image
Back
Compressed hypothesis testing: To mix or not to mix?
Conference proceeding

Compressed hypothesis testing: To mix or not to mix?

Weiyu Xu and Lifeng Lai
2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.1443-1449
10/2013
DOI: 10.1109/Allerton.2013.6736697

View Online

Abstract

In this paper, we study a hypothesis testing problem of, among n random variables, determining k random variables which have different probability distributions from the rest (n - k) random variables. Instead of using separate measurements of each individual random variable, we propose to use mixed measurements which are functions of multiple random variables. It is demonstrated that O(klog(n)/min P i , P j C(P i , P j )) equation observations are sufficient for correctly identifying the k anomalous random variables with a high probability, where C(P i , P j ) is the Chernoff information between two possible distributions P i and P j for the proposed mixed observations. We characterize the Chernoff information under fixed time-invariant mixed observations, random time-varying mixed observations and deterministic time-varying mixed observations respectively. For time-varying measurements, we introduce inner and outer conditional Chernoff information in our derivations. We demonstrate that mixed observations can strictly improve the error exponent of the hypothesis testing, over separate observations of individual random variables. These results imply that mixed observations of random variables can reduce the number of required samples in hypothesis testing applications. In contrast to the compressed sensing problems, this paper considers random variables whose values changes in different measurements.
 Compressed sensing Error probability Measurement uncertainty Probability distribution Random variables Testing Vectors

Details

Metrics

23 Record Views
Logo image