ML p(r)ior | Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-04-21
1904.09563 | cs.IT

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-11-30
1811.12804 | math.ST

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

Highlights - Most important sentences from the article

2019-01-18
1901.06214 | cs.IT

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-01-26
1801.08639 | cs.IT

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-01-02
1901.00555 | cs.IT

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article