Skip to content

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

Research output: Contribution to journalArticle

Original languageEnglish
Article number8423683
Pages (from-to)707-723
Number of pages17
JournalIEEE Transactions on Information Theory
Volume65
Issue number2
Early online date31 Jul 2018
DOIs
DateSubmitted - 21 Nov 2016
DateAccepted/In press - 12 Jul 2018
DateE-pub ahead of print - 31 Jul 2018
DatePublished (current) - 1 Feb 2019

Abstract

We consider the nonadaptive group testing with N items, of which K = Θ (N θ) 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.

    Research areas

  • Algorithm design and analysis, group testing, measurement design, performance bounds, sparse models

Download statistics

No data available

Documents

Documents

  • Full-text PDF (submitted manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via IEEE at https://ieeexplore.ieee.org/document/8423683/ . Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 768 KB, PDF document

DOI

View research connections

Related faculties, schools or groups