Improved group testing rates with constant column weight designs

Matthew P Aldridge; Oliver T Johnson; Jonathan Scarlett

doi:10.1109/ISIT.2016.7541525

Improved group testing rates with constant column weight designs

Matthew P Aldridge, Oliver T Johnson, Jonathan Scarlett

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

16 Citations (Scopus)

304 Downloads (Pure)

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	2016 IEEE International Symposium on Information Theory (ISIT 2016)
Subtitle of host publication	Proceedings of a meeting held 10-15 July 2016 at Barcelona, Spain
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	1381-1386
Number of pages	5
ISBN (Electronic)	9781509018062
ISBN (Print)	9781509018079
DOIs	https://doi.org/10.1109/ISIT.2016.7541525
Publication status	Published - 20 Aug 2016
Event	2016 IEEE International Symposium on Information Theory (ISIT) - Barcelona, Spain Duration: 10 Jul 2016 → 15 Jul 2016

Publication series

Name	Proceedings of the IEEE International Symposium on Information Theory (ISIT)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
ISSN (Print)	2157-8117

Conference

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

Access to Document

10.1109/ISIT.2016.7541525

Full-text PDF (accepted author manuscript)
This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Institute of Electrical and Electronics Engineers at http://dx.doi.org/10.1109/ISIT.2016.7541525.
Accepted author manuscript, 539 KB

http://arxiv.org/abs/1602.03471

Handle.net

Persistent link

Cite this

Aldridge, M. P., Johnson, O. T., & Scarlett, J. (2016). Improved group testing rates with constant column weight designs. In 2016 IEEE International Symposium on Information Theory (ISIT 2016) : Proceedings of a meeting held 10-15 July 2016 at Barcelona, Spain (pp. 1381-1386). (Proceedings of the IEEE International Symposium on Information Theory (ISIT)). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ISIT.2016.7541525

Aldridge, Matthew P ; Johnson, Oliver T ; Scarlett, Jonathan. / Improved group testing rates with constant column weight designs. 2016 IEEE International Symposium on Information Theory (ISIT 2016) : Proceedings of a meeting held 10-15 July 2016 at Barcelona, Spain. Institute of Electrical and Electronics Engineers (IEEE), 2016. pp. 1381-1386 (Proceedings of the IEEE International Symposium on Information Theory (ISIT)).

@inproceedings{10722d6875e648889f8271bd09b91b93,

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 = "Aldridge, {Matthew P} and Johnson, {Oliver T} and Jonathan Scarlett",

year = "2016",

month = aug,

day = "20",

doi = "10.1109/ISIT.2016.7541525",

language = "English",

isbn = "9781509018079",

series = "Proceedings of the IEEE International Symposium on Information Theory (ISIT)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

pages = "1381--1386",

booktitle = "2016 IEEE International Symposium on Information Theory (ISIT 2016)",

address = "United States",

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

}

Aldridge, MP, Johnson, OT & Scarlett, J 2016, Improved group testing rates with constant column weight designs. in 2016 IEEE International Symposium on Information Theory (ISIT 2016) : Proceedings of a meeting held 10-15 July 2016 at Barcelona, Spain. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Institute of Electrical and Electronics Engineers (IEEE), pp. 1381-1386, 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 10/07/16. https://doi.org/10.1109/ISIT.2016.7541525

Improved group testing rates with constant column weight designs. / Aldridge, Matthew P; Johnson, Oliver T; Scarlett, Jonathan.
2016 IEEE International Symposium on Information Theory (ISIT 2016) : Proceedings of a meeting held 10-15 July 2016 at Barcelona, Spain. Institute of Electrical and Electronics Engineers (IEEE), 2016. p. 1381-1386 (Proceedings of the IEEE International Symposium on Information Theory (ISIT)).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Improved group testing rates with constant column weight designs

AU - Aldridge, Matthew P

AU - Johnson, Oliver T

AU - Scarlett, Jonathan

PY - 2016/8/20

Y1 - 2016/8/20

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.

U2 - 10.1109/ISIT.2016.7541525

DO - 10.1109/ISIT.2016.7541525

M3 - Conference Contribution (Conference Proceeding)

SN - 9781509018079

T3 - Proceedings of the IEEE International Symposium on Information Theory (ISIT)

SP - 1381

EP - 1386

BT - 2016 IEEE International Symposium on Information Theory (ISIT 2016)

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 2016 IEEE International Symposium on Information Theory (ISIT)

Y2 - 10 July 2016 through 15 July 2016

ER -

Aldridge MP, Johnson OT, Scarlett J. Improved group testing rates with constant column weight designs. In 2016 IEEE International Symposium on Information Theory (ISIT 2016) : Proceedings of a meeting held 10-15 July 2016 at Barcelona, Spain. Institute of Electrical and Electronics Engineers (IEEE). 2016. p. 1381-1386. (Proceedings of the IEEE International Symposium on Information Theory (ISIT)). Epub 2016 Jul 10. doi: 10.1109/ISIT.2016.7541525

Improved group testing rates with constant column weight designs

Abstract

Publication series

Conference

Access to Document

Handle.net

Fingerprint

Cite this