Scarlett, Jonathan
Cevher, Volkan
Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices
2016 Ieee International Symposium On Information Theory
2016 Ieee International Symposium On Information Theory
2016 Ieee International Symposium On Information Theory
2016 Ieee International Symposium On Information Theory
5
Group testing
information-theoretic limits
converse bounds
Fano's inequality
2016
2016
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.
Ieee
978-1-5090-1806-2
2016 Ieee International Symposium On Information Theory
Conference Papers
000390098702187