On finding a subset of non-defective items from a large population using group tests: Recovery algorithms and bounds

Abstract

We present computationally efficient and analytically tractable algorithms for identifying a given number of “non-defective” items from a large population containing a small number of “defective” items under a noisy Non-adaptive Group Testing (NGT) framework. In contrast to the classical NGT, where the main goal is to identify the complete set of defective items, the main goal of a non-defective subset recovery algorithm is to identify a subset of non-defective items given the test outcomes. In this paper, we present three algorithms and corresponding bounds on the number of tests required for successful non-defective subset recovery. We consider a random, non-adaptive pooling strategy with noisy test outcomes, where we account for the impact of both additive noise (false positives) and dilution noise (false negatives). We provide simulation results to highlight the relative performance of the algorithms, and to demonstrate the significant improvement they offer over existing approaches, in terms of the number of tests required for a given success rate.