Matthew Aldridge

Matthew Aldridge

Auto-generated profile, based on publicly available information

Matthew Aldridge

School of Mathematics, University of Leeds, Leeds, U.K.

Research Focus & Metrics

Academic Career Length

17Years (2010-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
5 December 2019 in Foundations and Trends® in Communications and Information Theory
Verified
Journal Article
Closed access
PDF file
MAMatthew Aldridge
Matthew Aldridge
OJOliver Johnson
Oliver Johnson
Jonathan ScarlettJonathan Scarlett
Jonathan Scarlett
The group testing problem concerns discovering a small number of defective items within a large population by performing tests on pools of items. A test is positive if the pool contains at least one defective, and negative if it contains no defectives. This is a sparse inference problem with a combinatorial flavour, with applications in medical testing, biology, telecommunications, information technology, data science, and more. In this monograph, we survey recent developments in the group testing problem from an information-theoretic perspective. We cover several related developments: efficient algorithms with practical storage and computation requirements, achievability bounds for optimal decoding methods, and algorithm-independent converse bounds. We assess the theoretical guarantees not only in terms of scaling laws, but also in terms of the constant factors, leading to the notion of the rate of group testing, indicating the amount of information learned per test. Considering both noiseless and noisy settings, we identify several regimes where existing algorithms are provably optimal or near-optimal, as well as regimes where there remains greater potential for improvement. In addition, we survey results concerning a number of variations on the standard group testing problem, including partial recovery criteria, adaptive algorithms with a limited number of stages, constrained test designs, and sublinear-time algorithms.

31 March 2014 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
MAMatthew Aldridge
Matthew Aldridge
LBLeonardo Baldassini
Leonardo Baldassini
OJOliver Johnson
Oliver Johnson
We consider the problem of nonadaptive noiseless group testing of N items of which K are defective. We describe four detection algorithms, the COMP algorithm of Chan et al., two new algorithms, DD and SCOMP, which require stronger evidence to declare an item defective, and an essentially optimal but computationally difficult algorithm called SSS. We consider an important class of designs for the group testing problem, namely those in which the test structure is given via a Bernoulli random process. In this class of Bernoulli designs, by considering the asymptotic rate of these algorithms, we show that DD outperforms COMP, that DD is essentially optimal in regimes where K ≥ √N, and that no algorithm can perform as well as the best nonrandom adaptive algorithms when K > N 0.35 . In simulations, we see that DD and SCOMP far outperform COMP, with SCOMP very close to the optimal SSS, especially in cases with larger K.

31 July 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
OJOliver Johnson
Oliver Johnson
MAMatthew Aldridge
Matthew Aldridge
Jonathan ScarlettJonathan Scarlett
Jonathan Scarlett
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 analyse 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 COMP and 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 randomised 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.

5 October 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
MAMatthew Aldridge
Matthew Aldridge
We consider nonadaptive probabilistic group testing in the linear regime, where each of n items is defective independently with probability p ∈ (0, 1), and p is a constant independent of n. We show that testing each item individually is optimal, in the sense that with fewer than n tests the error probability is bounded away from zero.

1 July 2013
Verified
Conference Paper
Closed access
LBLeonardo Baldassini
Leonardo Baldassini
OJOliver Johnson
Oliver Johnson
MAMatthew Aldridge
Matthew Aldridge
We define capacity for group testing problems and deduce bounds for the capacity of a variety of noisy models, based on the capacity of equivalent noisy communication channels. For noiseless adaptive group testing we prove an information-theoretic lower bound which tightens a bound of Chan et al. This can be combined with a performance analysis of a version of Hwang's adaptive group testing algorithm, in order to deduce the capacity of noiseless and erasure group testing models.

4 September 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
MAMatthew Aldridge
Matthew Aldridge
We consider nonadaptive group testing with Bernoulli tests, where each item is placed in each test independently with some fixed probability. We give a tight threshold on the maximum number of tests required to find the defective set under optimal Bernoulli testing. Achievability is given by a result of Scarlett and Cevher; here we give a converse bound showing that this result is best possible. Our new converse requires three parts: a typicality bound generalising the trivial counting bound, a converse on the COMP algorithm of Chan et al., and a bound on the SSS algorithm similar to that given by Aldridge, Baldassini, and Johnson. Our result has a number of important corollaries, in particular that, in denser cases, Bernoulli nonadaptive group testing is strictly worse than the best adaptive strategies.