Group Testing Algorithms: Bounds and Simulations

M. Aldridge, Leonardo Baldassini, Oliver Johnson

Research output: Contribution to journalArticlepeer-review

50 Citations (Scopus)

Abstract

We consider the problem of nonadaptive noiseless group testing of N items of which K are defective. We describe four detection algorithms, the COMP algorithm of Chan et al., two new algorithms, DD and SCOMP, which require stronger evidence to declare an item defective, and an essentially optimal but computationally difficult algorithm called SSS. We consider an important class of designs for the group testing problem, namely those in which the test structure is given via a Bernoulli random process. In this class of Bernoulli designs, by considering the asymptotic rate of these algorithms, we show that DD outperforms COMP, that DD is essentially optimal in regimes where K ≥ √N, and that no algorithm can perform as well as the best nonrandom adaptive algorithms when K > N0.35. In simulations, we see that DD and SCOMP far outperform COMP, with SCOMP very close to the optimal SSS, especially in cases with larger K.
Original languageEnglish
Pages (from-to)3671-3687
Number of pages17
JournalIEEE Transactions on Information Theory
Volume60
Issue number6
Early online date31 Mar 2014
DOIs
Publication statusPublished - 1 Jun 2014

Keywords

  • combinatorial mathematics
  • compressed sensing
  • optimisation
  • Bernoulli random process
  • COMP algorithm
  • DD algorithms
  • SCOMP algorithms
  • SSS algorithm
  • combinatorial optimisation problem
  • detection algorithms
  • nonadaptive noiseless group testing algorithm
  • nonrandom adaptive algorithms
  • Algorithm design and analysis
  • Decoding
  • Detection algorithms
  • Inference algorithms
  • Matching pursuit algorithms
  • Testing
  • Upper bound
  • group testing
  • sparse models

Fingerprint Dive into the research topics of 'Group Testing Algorithms: Bounds and Simulations'. Together they form a unique fingerprint.

Cite this