Conference paper

Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

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.

Related material