Near-Optimal Noisy Group Testing via Separate Decoding of Items

Abstract

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. In this paper, we revisit an efficient algorithm for noisy group testing in which each item is decoded separately (Malyutov and Mateev, 1980), and develop novel performance guarantees via an information-theoretic framework for general noise models. For the special cases of no noise and symmetric noise, we find that the asymptotic number of tests required for vanishing error probability is within a factor $\log 2\approx 0.7$ of the information-theoretic optimum at low sparsity levels, and that with a small fraction of allowed incorrectly decoded items, this guarantee extends to all sublinear sparsity levels. In addition, we provide a converse bound showing that if one tries to move slightly beyond our low-sparsity achievability threshold using separate decoding of items and i.i.d. randomized testing, the average number of items decoded incorrectly approaches that of a trivial decoder.

Submitted to IEEE Journal of Selected Topics in Signal Processing

References in corpus (1)

• On the optimality of some group testing algorithms

Cited by in corpus (12)

• Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design
• Improved bounds for noisy group testing with constant tests per item
• On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing
• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
• On the All-Or-Nothing Behavior of Bernoulli Group Testing
• Group testing and local search: is there a computational-statistical gap?
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
• Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
• Nearly Optimal Sparse Group Testing
• Generalized Group Testing
• An Efficient Algorithm for Capacity-Approaching Noisy Adaptive Group Testing