Improved group testing rates with constant column weight designs

Matthew Aldridge; Oliver Johnson; Jonathan Scarlett

doi:10.1109/ISIT.2016.7541525

Improved group testing rates with constant column weight designs

Matthew Aldridge, Oliver Johnson, Jonathan Scarlett

Department of Mathematical Sciences

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

14 Citations (SciVal)

Abstract

We consider nonadaptive group testing where each item is placed in a constant number of tests. The tests are chosen uniformly at random with replacement, so the testing matrix has (almost) constant column weights. We show that performance is improved compared to Bernoulli designs, where each item is placed in each test independently with a fixed probability. In particular, we show that the rate of the practical COMP detection algorithm is increased by 31% in all sparsity regimes. In dense cases, this beats the best possible algorithm with Bernoulli tests, and in sparse cases is the best proven performance of any practical algorithm. We also give an algorithm-independent upper bound for the constant column weight case; for dense cases this is again a 31% increase over the analogous Bernoulli result.

Original language	English
Title of host publication	Proceedings of IEEE International Symposium on Information Theory, 2016
Publisher	IEEE
Pages	1381-1385
Number of pages	5
ISBN (Print)	9781509018062
DOIs	https://doi.org/10.1109/ISIT.2016.7541525
Publication status	Published - 10 Aug 2016
Event	2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: 10 Jul 2016 → 15 Jul 2016

Conference

Conference	2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/Territory	Spain
City	Barcelona
Period	10/07/16 → 15/07/16

Access to Document

10.1109/ISIT.2016.7541525

Cite this

@inproceedings{138639ab5a5f4d6c89fcf76b360abe1f,

title = "Improved group testing rates with constant column weight designs",

abstract = "We consider nonadaptive group testing where each item is placed in a constant number of tests. The tests are chosen uniformly at random with replacement, so the testing matrix has (almost) constant column weights. We show that performance is improved compared to Bernoulli designs, where each item is placed in each test independently with a fixed probability. In particular, we show that the rate of the practical COMP detection algorithm is increased by 31% in all sparsity regimes. In dense cases, this beats the best possible algorithm with Bernoulli tests, and in sparse cases is the best proven performance of any practical algorithm. We also give an algorithm-independent upper bound for the constant column weight case; for dense cases this is again a 31% increase over the analogous Bernoulli result.",

author = "Matthew Aldridge and Oliver Johnson and Jonathan Scarlett",

year = "2016",

month = aug,

day = "10",

doi = "10.1109/ISIT.2016.7541525",

language = "English",

isbn = "9781509018062",

pages = "1381--1385",

booktitle = "Proceedings of IEEE International Symposium on Information Theory, 2016",

publisher = "IEEE",

address = "USA United States",

note = "2016 IEEE International Symposium on Information Theory, ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

}

TY - GEN

T1 - Improved group testing rates with constant column weight designs

AU - Aldridge, Matthew

AU - Johnson, Oliver

AU - Scarlett, Jonathan

PY - 2016/8/10

Y1 - 2016/8/10

N2 - We consider nonadaptive group testing where each item is placed in a constant number of tests. The tests are chosen uniformly at random with replacement, so the testing matrix has (almost) constant column weights. We show that performance is improved compared to Bernoulli designs, where each item is placed in each test independently with a fixed probability. In particular, we show that the rate of the practical COMP detection algorithm is increased by 31% in all sparsity regimes. In dense cases, this beats the best possible algorithm with Bernoulli tests, and in sparse cases is the best proven performance of any practical algorithm. We also give an algorithm-independent upper bound for the constant column weight case; for dense cases this is again a 31% increase over the analogous Bernoulli result.

AB - We consider nonadaptive group testing where each item is placed in a constant number of tests. The tests are chosen uniformly at random with replacement, so the testing matrix has (almost) constant column weights. We show that performance is improved compared to Bernoulli designs, where each item is placed in each test independently with a fixed probability. In particular, we show that the rate of the practical COMP detection algorithm is increased by 31% in all sparsity regimes. In dense cases, this beats the best possible algorithm with Bernoulli tests, and in sparse cases is the best proven performance of any practical algorithm. We also give an algorithm-independent upper bound for the constant column weight case; for dense cases this is again a 31% increase over the analogous Bernoulli result.

UR - http://www.scopus.com/inward/record.url?scp=84985947060&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541525

DO - 10.1109/ISIT.2016.7541525

M3 - Chapter in a published conference proceeding

AN - SCOPUS:84985947060

SN - 9781509018062

SP - 1381

EP - 1385

BT - Proceedings of IEEE International Symposium on Information Theory, 2016

PB - IEEE

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -

Improved group testing rates with constant column weight designs

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this