How little does non-exact recovery help in group testing?

We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of tests. We characterize the information-theoretic performance limits in the presence of list decoding, in which the decoder may output a list containing more elements than the number of defectives, and the only requirement is that the true defective set is a subset of the list, or more generally, that their overlap exceeds a given threshold. We show that even under this highly relaxed criterion, in several scaling regimes the asymptotic number of tests is no smaller than the exact recovery setting. However, we also provide examples where a reduction is provably attained. We support our theoretical findings with numerical experiments.


Published in:
2017 Ieee International Conference On Acoustics, Speech And Signal Processing (Icassp), 6090-6094
Presented at:
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, March 2017
Year:
2017
Publisher:
New York, Ieee
ISSN:
1520-6149
ISBN:
978-1-5090-4117-6
Keywords:
Laboratories:




 Record created 2017-02-10, last modified 2018-01-28

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)