On Finding a Subset of Non-Defective Items From a Large Population.

In this paper, we derive mutual information based upper bounds on the number of nonadaptive group tests required to identify a given number of “non-defective” items from a large population containing a small number of “defective” items. In the asymptotic regime with the population size $N \rightarrow \infty$ , to identify $L$ nondefective items out of a population containing $K$ defective items, our results show that $\frac{C_s K}{1-o(1)} (\Phi (\alpha _0, \beta _0) + o(1))$ measurements are sufficient when the tests are reliable. Here, $C_s$ is a constant independent of $N, K$ , and $L$ , and $\Phi (\alpha _0, \beta _0)$ is a bounded function of $\alpha _0 \triangleq \lim _{N\rightarrow \infty } \frac{L}{N-K}$ and $\beta _0 \triangleq \lim _{N\rightarrow \infty } \frac{K}{N-K}$. In contrast, the necessary number of tests using the conventional approach of first identifying the $K$ defective items and picking the required number of nondefective items from the complement set grows with $N$ as $O\left(K \log N \right)$. We also derive upper bounds on the number of tests under both dilution and additive noise models. Our results are obtained under a very general sparse signal model, by virtue of which, they are also applicable to other important sparse signal based applications such as compressive sensing. [ABSTRACT FROM AUTHOR]