Boolean Compressed Sensing and Noisy Group Testing

Details Boolean Compressed Sensing and Noisy Group Testing Boolean Compressed Sensing and Noisy Group Testing

2009-07-06

arxiv.org/abs/0907.1061v4

Computer Science

Information Theory

In this revision: reorganized the paper, fixed some bugs and added an appendix. This is the revised version of the journal sub

Scientific paper

The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. The single letter characterization is shown to be tight for many interesting noisy group testing scenarios. Specifically, we consider an additive Bernoulli(q) noise model where we show that, for N items and K defectives, the number of tests T is O(K log N/(1-q)) for arbitrarily small average error probability and O(K^2 log N/(1-q)) for a worst case error criterion. We also consider dilution effects whereby a defective item in a positive pool might get diluted with probability u and potentially missed. In this case, it is shown that T is O(K log N/(1-u)^2) and O(K^2 log N/(1-u)^2) for the average and the worst case error criteria, respectively. Furthermore, our bounds allow us to verify existing known bounds for noiseless group testing including the deterministic noise-free case and approximate reconstruction with bounded distortion. Our proof of achievability is based on random coding and the analysis of a Maximum Likelihood Detector, and our information theoretic lower bound is based on Fano's inequality.

Affiliated with

Also associated with

No associations

Rating

Boolean Compressed Sensing and Noisy Group Testing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boolean Compressed Sensing and Noisy Group Testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boolean Compressed Sensing and Noisy Group Testing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-28371