Near-Optimal Noisy Group Testing via Separate Decoding of Items
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 approximate to 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 independent identically distributed randomized testing, the average number of items decoded incorrectly approaches that of a trivial decoder.
Near-Optimal Noisy.pdf
Postprint
openaccess
337.37 KB
Adobe PDF
0f3a5f1a54327ffd965c6ed99070825a
SeparateGT_2COL.pdf
Publisher's version
openaccess
508.35 KB
Adobe PDF
a5dcd7195f8911856d4b1ca01daf0b9a