On Finding a Subset of Healthy Individuals from a Large Population

In this paper, we derive mutual information based upper and lower 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. We show that a reduction in the number of tests is achievable compared to the approach of first identifying all the defective items and then picking the required number of non-defective items from the complement set. In the asymptotic regime with the population size $N \rightarrow \infty$,toidentify$L$ non-defective items out of a population containing $K$ defective items, when the tests are reliable, our results show that $\frac{C_{s}K}{1-o(1)}(\mathrm{\Phi }({\alpha }_0,{\beta }_0)+o(1))$ measurements are sufficient, where $C_s$ is a constant independent of $N,K$ and $L$, and $\mathrm{\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}$. Further, in the nonadaptive group testing setup, we obtain rigorous upper and lower bounds on the number of tests under both dilution and additive noise models. Our results are derived using a general sparse signal model, by virtue of which, they are also applicable to other important sparse signal based applications such as compressive sensing.