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.

本论文提出了一种新的信息论视角用于组测问题的建模，并且基于随机编码和最大似然检测器分析导出了总测试次数的单字母特征公式，并使用 Bernoulli 噪声模型和混水效应考虑了多种情况并得到了对应的较为紧凑的渐进界，同时可以验证现有无噪声情况下的渐进界以及带有绑定扭曲的近似重构。