### Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

**2016-02-02**

1602.00875 | cs.IT

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.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-04-18**

1904.08576 | cs.LG

A growing number of modern statistical learning problems involve estimating a
large number of parame… show more

**2018-03-08**

1803.03287 | cs.IT

In Group Synchronization, one attempts to find a collection of unknown group
elements from noisy mea… show more

**2019-04-21**

1904.09563 | cs.IT

The task of manipulating correlated random variables in a distributed setting
has received attention… show more

**2018-11-12**

1811.04734 | cs.IT

Shannon's mutual information of a random multiple antenna and multipath
channel is studied in the ge… show more

**2019-01-30**

1901.10647 | cs.IT

The support recovery problem consists of determining a sparse subset of
variables that is relevant i… show more

**2019-02-06**

1902.02202 | cs.DM

In the group testing problem we aim to identify a small number of infected
individuals within a larg… show more

**2017-08-11**

1708.03429 | cs.IT

Group testing is the process of pooling arbitrary subsets from a set of $n$
items so as to identify,… show more

**2018-08-04**

1808.01457 | cs.IT

We consider the probabilistic group testing problem where $d$ random
defective items in a large popu… show more

**2018-11-30**

1811.12804 | math.ST

This paper is concerned with a curious phenomenon in spectral estimation.
Suppose we are interested … show more

**2019-01-18**

1901.06214 | cs.IT

Group-sparsity is a common low-complexity signal model with widespread
application across various do… show more

**2019-02-01**

1902.00141 | cs.LG

We consider the problem of learning the qualities of a collection of items by
performing noisy compa… show more

**2018-01-26**

1801.08639 | cs.IT

This paper deals with two related problems, namely distance-preserving binary
embeddings and quantiz… show more

**2015-06-02**

1506.00898 | stat.ML

This paper studies the problem of estimating the covariance of a collection
of vectors using only hi… show more

**2016-07-12**

1607.03519 | cs.IT

We investigate the maximum coding rate for a given average blocklength and
error probability over a … show more

**2019-01-02**

1901.00555 | cs.IT

Information theory plays an indispensable role in the development of
algorithm-independent impossibi… show more

**2017-12-20**

1712.07509 | cs.IT

We consider non-adaptive threshold group testing for identification of up to
$d$ defective items in … show more