On Finding a Subset of Healthy Individuals from a Large Population

Abstract

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\to \infty$, to identify $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)}(\Phi ({\alpha }_0,{\beta }_0)+o(1))$ measurements are sufficient, where $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\to \infty }\frac{L}{N-K}$ and ${\beta }_0\triangleq {\lim }_{N\to \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.

32 pages, 2 figures, 3 tables, revised version of a paper submitted to IEEE Trans. Inf. Theory

References in corpus (3)

• The Capacity of Adaptive Group Testing
• Non-adaptive Group Testing: Explicit bounds and novel algorithms
• Finding Zeros: Greedy Detection of Holes