Skip to content

Performance of Group Testing Algorithms With Near-Constant Tests-per-Item

Research output: Contribution to journalArticle

Standard

Performance of Group Testing Algorithms With Near-Constant Tests-per-Item. / Johnson, Oliver; Aldridge, Matthew P; Scarlett, Jonathan.

In: IEEE Transactions on Information Theory, Vol. 65, No. 2, 8423683, 01.02.2019, p. 707-723.

Research output: Contribution to journalArticle

Harvard

Johnson, O, Aldridge, MP & Scarlett, J 2019, 'Performance of Group Testing Algorithms With Near-Constant Tests-per-Item', IEEE Transactions on Information Theory, vol. 65, no. 2, 8423683, pp. 707-723. https://doi.org/10.1109/TIT.2018.2861772

APA

Johnson, O., Aldridge, M. P., & Scarlett, J. (2019). Performance of Group Testing Algorithms With Near-Constant Tests-per-Item. IEEE Transactions on Information Theory, 65(2), 707-723. [8423683]. https://doi.org/10.1109/TIT.2018.2861772

Vancouver

Johnson O, Aldridge MP, Scarlett J. Performance of Group Testing Algorithms With Near-Constant Tests-per-Item. IEEE Transactions on Information Theory. 2019 Feb 1;65(2):707-723. 8423683. https://doi.org/10.1109/TIT.2018.2861772

Author

Johnson, Oliver ; Aldridge, Matthew P ; Scarlett, Jonathan. / Performance of Group Testing Algorithms With Near-Constant Tests-per-Item. In: IEEE Transactions on Information Theory. 2019 ; Vol. 65, No. 2. pp. 707-723.

Bibtex

@article{3a660d945c454b40960202db6b79f865,
title = "Performance of Group Testing Algorithms With Near-Constant Tests-per-Item",
abstract = "We consider the nonadaptive group testing with N items, of which K = Θ (N θ) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23{\%} fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for θ > 0.43 and the best proven performance with a practical decoding algorithm for all θ ∞ (0,1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when θ > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.",
keywords = "Algorithm design and analysis, group testing, measurement design, performance bounds, sparse models",
author = "Oliver Johnson and Aldridge, {Matthew P} and Jonathan Scarlett",
year = "2019",
month = "2",
day = "1",
doi = "10.1109/TIT.2018.2861772",
language = "English",
volume = "65",
pages = "707--723",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "2",

}

RIS - suitable for import to EndNote

TY - JOUR

T1 - Performance of Group Testing Algorithms With Near-Constant Tests-per-Item

AU - Johnson, Oliver

AU - Aldridge, Matthew P

AU - Scarlett, Jonathan

PY - 2019/2/1

Y1 - 2019/2/1

N2 - We consider the nonadaptive group testing with N items, of which K = Θ (N θ) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for θ > 0.43 and the best proven performance with a practical decoding algorithm for all θ ∞ (0,1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when θ > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.

AB - We consider the nonadaptive group testing with N items, of which K = Θ (N θ) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for θ > 0.43 and the best proven performance with a practical decoding algorithm for all θ ∞ (0,1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when θ > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.

KW - Algorithm design and analysis

KW - group testing

KW - measurement design

KW - performance bounds

KW - sparse models

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

UR - https://arxiv.org/abs/1612.07122

U2 - 10.1109/TIT.2018.2861772

DO - 10.1109/TIT.2018.2861772

M3 - Article

VL - 65

SP - 707

EP - 723

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 2

M1 - 8423683

ER -