Performance of Group Testing Algorithms With Near-Constant Tests Per Item

We consider the nonadaptive group testing with N items, of which K = Theta (N-theta) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for theta > 0.43 and the best proven performance with a practical decoding algorithm for all theta is an element of(0, 1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when theta > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.