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

Oliver Johnson, Matthew Aldridge, Jonathan ScarlettIEEE Trans. Information Theory 2019 · OpenReview

TL;DR

This paper introduces a novel "near-constant column weight" design for nonadaptive group testing that significantly reduces the number of tests required compared to standard Bernoulli designs. By pairing this design with practical decoding algorithms like COMP and DD, the authors achieve substantial performance improvements, especially in denser scenarios, and demonstrate near-optimality for certain parameter ranges.

What Problem Does This Paper Address?

Group testing is a powerful technique for identifying defective items within a large population using pooled tests. The goal is to minimize the total number of tests while accurately identifying all defective items. A key challenge is designing efficient "test matrices" (which items go into which pools) and decoding algorithms, particularly in the "nonadaptive" setting where all tests are planned in advance. Existing methods, like the "Bernoulli design," where each item is independently included in tests with a fixed probability, are well-studied but can be inefficient, especially when the number of defective items is not extremely sparse. This paper aims to improve the performance of nonadaptive group testing by proposing a new test design that requires fewer tests and is amenable to practical decoding algorithms.

Methods

The core contribution is a new test design called the "near-constant column weight" design. In this design, each item is placed into a fixed number of tests, chosen uniformly at random. This contrasts with the Bernoulli design, where each item's inclusion in a test is an independent random event with a fixed probability. The authors then analyze the performance of this new design when paired with two decoding algorithms:

  • COMP (Combinatorial Orthogonal Matching Pursuit): A simple algorithm that marks items appearing in negative tests as non-defective.
  • DD (Definite Defectives): An algorithm that builds on COMP by identifying items that are the only possible defective item in a positive test.

The analysis involves rigorous theoretical bounds, including asymptotic results and converse theorems, to establish achievable rates of information recovery per test. They also provide simulations to validate their theoretical findings.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations, not on training or evaluating on specific real-world datasets.

Key Insights and Ideas

  • The "Near-Constant Column Weight" Design is Key: The core insight is that ensuring each item participates in roughly the same number of tests (controlled by the parameter $L$) leads to significant efficiency gains over the Bernoulli design, where item participation can vary widely.
  • Practical Algorithms Shine: The paper demonstrates that even simple, practical decoding algorithms like COMP and DD achieve substantial improvements with the new design, outperforming more complex or impractical algorithms used with Bernoulli designs.
  • Optimality in Certain Regimes: For the near-constant column weight design, the DD algorithm is shown to be optimal when the density of defective items ($\theta$) is greater than or equal to 1/2.
  • Trade-off Between Design and Decoding: The analysis highlights how the choice of test design strongly influences the performance of decoding algorithms, and how a well-chosen design can compensate for simpler decoding strategies.

Key Results

  • Significant Test Reduction: The new design requires approximately 23.4% fewer tests compared to Bernoulli designs for both COMP and DD algorithms.
  • Improved Performance for COMP: For $\theta > 0.766$, COMP with the new design outperforms even optimal algorithms used with Bernoulli designs. The achievable rate for COMP is $0.693(1-\theta)$, a 30.6% improvement over Bernoulli designs.
  • Improved Performance for DD: For $\theta > 0.434$, DD with the new design outperforms any algorithm (even impractical ones) with Bernoulli designs. The achievable rate for DD is $0.693 \min(1, \frac{1-\theta}{\theta})$, which is optimal for $\theta \ge 1/2$.
  • Theoretical Converse: An algorithm-independent converse bound shows that the DD algorithm's performance is near-optimal for the near-constant column weight design when $\theta \ge 1/2$.
  • Simulation Validation: Simulations confirm the theoretical improvements, showing notable gains for the new design over Bernoulli designs in both sparse and dense scenarios.

Limitations and Future Work

  • Optimality for $\theta < 1/2$: While the DD algorithm performs well for $\theta \ge 1/2$, it remains an open problem to determine the maximum achievable rate for $\theta < 1/2$ with near-constant column weight designs. The authors conjecture that the converse bound (Theorem 4) is achievable by practical algorithms.
  • Practicality of Other Algorithms: The paper focuses on COMP and DD as "practical" algorithms. It's an open question whether other algorithms, like SCOMP or those based on linear programming, can further improve performance beyond DD.
  • Achieving Rate 1: It's an open question whether a rate of 1 (perfect recovery) can be achieved for values of $\theta$ beyond $0.409$ using constant or near-constant column weight designs.
  • Adaptivity Gap: The existence of an "adaptivity gap" – a scenario where nonadaptive testing fundamentally limits performance compared to adaptive testing – remains an open area of research.

Summary updated

Abstract

We consider the nonadaptive group testing with N items, of which K = Θ(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">θ</sup> ) 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 θ > 0.43 and the best proven performance with a practical decoding algorithm for all θ ∈ (0, 1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when θ > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.
BibTeX
@article{johnson2019performance,
  author = {Oliver Johnson and Matthew Aldridge and Jonathan Scarlett},
  title = {{Performance of Group Testing Algorithms With Near-Constant Tests Per Item}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=rBxPfxi1vx9},
}

Loading related content...

Figure