  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 order-wise 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(\frac{K\log N}{1-q})$ for arbitrarily
small average error probability and $O(\frac{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(\frac{K\log N}{(1-u)^2})$ and
$O(\frac{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.
