TY - CPAPER
AB - 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 noisy tests. While matching achievability and converse bounds are known in several cases of interest for i.i.d.~measurement matrices, less is known regarding converse bounds for arbitrary measurement matrices. We address this by presenting two converse bounds for arbitrary matrices and general noise models. First, we provide a strong converse bound ($\mathbb{P}[\mathrm{error}] \to 1$) that matches existing achievability bounds in several cases of interest. Second, we provide a weak converse bound ($\mathbb{P}[\mathrm{error}] \not\to 0$) that matches existing achievability bounds in greater generality.
T1 - Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices
DA - 2016
AU - Scarlett, Jonathan
AU - Cevher, Volkan
JF - 2016 Ieee International Symposium On Information Theory
SP - 2868-2872
EP - 2868-2872
PB - Ieee
PP - New York
ID - 215128
KW - Group testing
KW - information-theoretic limits
KW - converse bounds
KW - Fano's inequality
SN - 978-1-5090-1806-2
UR - http://infoscience.epfl.ch/record/215128/files/GT_ISIT.pdf
ER -