Jonathan Scarlett

Dr. Jonathan Scarlett

National University of Singapore
orcid

Research Focus & Metrics

Academic Career Length

16Years (2011-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.

2 May 2018 in IEEE Transactions on Medical Imaging
Verified
Journal Article
Closed access
BGBaran Gozcu
Baran Gozcu
RMRabeeh Karimi Mahabadi
Rabeeh Karimi Mahabadi
YLYen-Huan Li
Yen-Huan Li
EIEfe Ilicak
Efe Ilicak
TÇTolga Çukur
Tolga Çukur
VCVolkan Cevher
Volkan Cevher
In the area of magnetic resonance imaging (MRI), an extensive range of non-linear reconstruction algorithms has been proposed which can be used with general Fourier subsampling patterns. However, the design of these subsampling patterns has typically been considered in isolation from the reconstruction rule and the anatomy under consideration. In this paper, we propose a learning-based framework for optimizing MRI subsampling patterns for a specific reconstruction rule and anatomy, considering both the noiseless and noisy settings. Our learning algorithm has access to a representative set of training signals, and searches for a sampling pattern that performs well on average for the signals in this set. We present a novel parameter-free greedy mask selection method and show it to be effective for a variety of reconstruction rules and performance metrics. Moreover, we also support our numerical findings by providing a rigorous justification of our framework via statistical learning theory.

21 October 2016 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Jonathan ScarlettJonathan Scarlett
Jonathan Scarlett
VTVincent Tan
Vincent Tan
GDGiuseppe Durisi
Giuseppe Durisi
We study the second-order asymptotics of information transmission using random Gaussian codebooks and nearest neighbor decoding over a power-limited stationary memoryless additive non-Gaussian noise channel. We show that the dispersion term depends on the non-Gaussian noise only through its second and fourth moments, thus complementing the capacity result (Lapidoth, 1996), which depends only on the second moment. Furthermore, we characterize the second-order asymptotics of point-to-point codes over K-sender interference networks with non-Gaussian additive noise. Specifically, we assume that each user's codebook is Gaussian and that NN decoding is employed, i.e., that interference from the K -1 unintended users (Gaussian interfering signals) is treated as noise at each decoder. We show that while the first-order term in the asymptotic expansion of the maximum number of messages depends on the power of the interfering codewords only through their sum, this does not hold for the second-order term.

8 September 2016 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Jonathan ScarlettJonathan Scarlett
Jonathan Scarlett
VCVolkan Cevher
Volkan Cevher
The support recovery problem consists of determining a sparse subset of a set of variables that is relevant in generating a set of observations, and arises in a diverse range of settings, such as compressive sensing, subset selection in regression, and group testing. In this paper, we take a unified approach to support recovery problems, considering general probabilistic models relating a sparse data vector to an observation vector. We study the information-theoretic limits of both exact and partial support recovery, taking a novel approach motivated by thresholding techniques in channel coding. We provide general achievability and converse bounds characterizing the trade-off between the error probability and number of measurements, and we specialize these to the linear, 1-bit, and group testing models. In several cases, our bounds not only provide matching scaling laws in the necessary and sufficient number of measurements, but also sharp thresholds with matching constant factors. Our approach has several advantages over previous approaches. For the achievability part, we obtain sharp thresholds under broader scalings of the sparsity level and other parameters (e.g., signal-to-noise ratio) compared with several previous works, and for the converse part, we not only provide conditions under which the error probability fails to vanish, but also conditions under which it tends to one.

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.

28 November 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Jonathan ScarlettJonathan Scarlett
Jonathan Scarlett
The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly noisy tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and many more. One of the defining features of the group testing problem is the distinction between the non-adaptive and adaptive settings. In the non-adaptive case, all tests must be designed in advance, whereas in the adaptive case, each test can be designed based on the previous outcomes. While tight information-theoretic limits and near-optimal practical algorithms are known for the adaptive setting in the absence of noise, surprisingly little is known in the noisy adaptive setting. In this paper, we address this gap by providing information-theoretic achievability and converse bounds under various noise models, as well as a slightly weaker achievability bound for a computationally efficient variant. These bounds are shown to be tight or near-tight in a broad range of scaling regimes, particularly at low noise levels. The algorithms used for the achievability results have the notable feature of only using two or three stages of adaptivity.