Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Near-Optimal Noisy Group Testing via Separate Decoding of Items
 
research article

Near-Optimal Noisy Group Testing via Separate Decoding of Items

Scarlett, Jonathan  
•
Cevher, Volkan  orcid-logo
October 1, 2018
IEEE Journal of Selected Topics In Signal Processing

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.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1109/JSTSP.2018.2844818
Web of Science ID

WOS:000446341300007

Author(s)
Scarlett, Jonathan  
Cevher, Volkan  orcid-logo
Date Issued

2018-10-01

Published in
IEEE Journal of Selected Topics In Signal Processing
Volume

12

Issue

5

Start page

902

End page

915

Subjects

Engineering, Electrical & Electronic

•

Engineering

•

group testing

•

sparsity

•

approximate recovery

•

information-theoretic methods

•

binary hypothesis testing

•

algorithms

•

recovery

•

matrices

•

bounds

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Available on Infoscience
December 13, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/152455
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés