About: In this paper, we consider the non-adaptive group testing problem in the linear sparsity regime. We prove a strong converse bound for exact recovery, showing that individual testing is asymptotically optimal for any non-zero target success probability, and strengthening the existing weak converse (Aldridge, 2019). To overcome this barrier, we additionally study an approximate recovery criterion. We demonstrate broad scenarios in which randomized test designs can improve on individual testing under this relaxed criterion, and provide a rate-distortion type converse.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : wasabi.inria.fr associated with source document(s)

AttributesValues
type
value
  • In this paper, we consider the non-adaptive group testing problem in the linear sparsity regime. We prove a strong converse bound for exact recovery, showing that individual testing is asymptotically optimal for any non-zero target success probability, and strengthening the existing weak converse (Aldridge, 2019). To overcome this barrier, we additionally study an approximate recovery criterion. We demonstrate broad scenarios in which randomized test designs can improve on individual testing under this relaxed criterion, and provide a rate-distortion type converse.
subject
  • Information theory
  • Design of experiments
  • Conjugate prior distributions
  • Elementary arithmetic
  • Factorial and binomial topics
  • Integers
  • Exponential family distributions
  • Indian inventions
  • Combinatorics
  • 0 (number)
  • Analysis of algorithms
  • Discrete distributions
  • Sparse matrices
  • Data compression
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software