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

Highlights - Most important sentences from the article

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
PDF

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
PDF

Highlights - Most important sentences from the article

2019-04-21

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

Highlights - Most important sentences from the article

2018-11-12

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

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
PDF

Highlights - Most important sentences from the article

2019-02-06

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

Highlights - Most important sentences from the article

2017-08-11

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

Highlights - Most important sentences from the article

2018-08-04

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

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
PDF

Highlights - Most important sentences from the article

2019-01-18

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

Highlights - Most important sentences from the article

2019-02-01

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

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
PDF

Highlights - Most important sentences from the article

2015-06-02

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

Highlights - Most important sentences from the article

2016-07-12

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

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
PDF

Highlights - Most important sentences from the article

2017-12-20

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

Highlights - Most important sentences from the article