The Noisy Quantitative Group Testing Problem

Tenghao Li, Neha Sangwan, Xiaxin Li, Arya Mazumdar · 2026

Read The Noisy Quantitative Group Testing Problem by Tenghao Li, Neha Sangwan, Xiaxin Li, Arya Mazumdar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11797.txt.

Introduction

Tenghao Li, Neha Sangwan, Xiaxin Li, and Arya Mazumdar study group testing when counts are noisy. In group testing, pools of samples are tested at once to find the few bad ones. The quantitative form asks how many bad ones sit in each pool.

They study three cases: no noise, added Gaussian noise, and a one-way noisy channel. For each case they test two methods. One scores links in a linear way, and one uses least squares fits. The work maps how well each method does as noise grows, which guides test design in labs.

Catalog record

CREATORTenghao Li, Neha Sangwan, Xiaxin Li, Arya Mazumdar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-11797

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Noisy Quantitative Group Testing Problem Tenghao Li, Neha Sangwan, Xiaxin Li, Arya Mazumdar Abstract In this paper, we study the problem of quantitative group testing (QGT) and analyze the performance of three models: the noiseless model, the additive Gaussian noise model, and the noisy Z-channel model. For each model, we analyze two algorithmic approaches: a linear estimator based on correlation scores, and a least squares estimator (LSE). We derive upper bounds on the number of tests required for exact recovery with vanishing error probability, and complement these results with information-theoretic lower bounds. In the additive Gaussian noise setting, our lower and upper bounds match in order. 1 Introduction Quantitative group testing (QGT) [ 3 ] [ 4 ] [ 9 ] generalizes classical group testing by observing, for each pooled test, the number of defectives in the pool. Compared with binary outcomes, quantitative measurements can substantially reduce the number of tests required for exact support recovery and can enable simple and efficient decoding algorithms. In this work, we study QGT under a non-adaptive random testing design in the sublinear regime, where the number of defectives grows sublinearly with the total number of items, and we focus on three canonical observation models. 1.1 Noiseless Model In the noiseless QGT model, each test returns the exact number of defective items included in the pool. This setting serves as a clean baseline and highlights the fundamental advantages of quantitative measurements in the absence of uncertainty. The noiseless model is well studied in the literature. In the dense regime, where the fraction of defectives is constant, sharp information-theoretic thresholds were characterized by Alaoui et al. [ 1 ] and Scarlett and Cevher [ 16 ] . These results were later extended to sparse and sublinear regimes by Gebhard et al. [ 4 ] , who derived sharp thresholds for high-probability recovery. Feige and Lellouche [ 3 ] showed that many polynomial-time algorithms require significantly more tests than information-theoretic limits and demonstrated improved recovery via reductions to structured subset selection problems. On the algorithmic side, a variety of non-adaptive decoding strategies have been proposed. Gebhard et al. [ 4 ] introduced a greedy reconstruction algorithm, while coding-theoretic constructions based on sparse graph codes were developed by Karimi et al. [ 9 ] . More recently, Hahn-Klimroth et al. [ 7 ] proposed a polynomial-time algorithm achieving near optimal number of tests. Overall, in the absence of noise, it is widely accepted that \Theta(k\log(n/k)/\log k) non-adaptive tests are both necessary and sufficient for exact recovery. [ 2 ] . 1.2 Additive Gaussian Noise Model In many practical settings, pooled measurements are corrupted by continuous noise, motivating the additive Gaussian noise QGT model [ 7 , 18 ] . In this model, each test outcome is perturbed by independent Gaussian noise, as commonly encountered in analog sensing and aggregated physical measurements. Dedicated studies of additive Gaussian noise in QGT have emerged only recently. Hahn-Klimroth and Kaaser [ 6 ] analyzed a greedy correlation-based decoder and characterized regimes of noise variance under which exact recovery is possible with high probability. Their result shows that for moderate noise levels, recovery is achievable with on the order of \Theta(k\log n) tests. However, no prior work has established tight information-theoretic achievability and converse bounds for Gaussian QGT. Our work addresses this gap by deriving matching upper and lower bounds on the sample complexity and by comparing the performance of practical decoders to these fundamental limits. 1.3 Noisy Z-Channel The noisy Z-channel model captures asymmetric item-level unreliability. In this setting, each defective item included in a test may independently fail to contribute to the observed count, leading to false negatives but no false positives. Hahn-Klimroth and Kaaser [ 6 ] studied a related noisy channel model in which each item’s state flips with a certain probability prior to pooling. This framework includes symmetric flip noise and, as a special case, one-sided error models. They showed that a greedy decoding algorithm can exactly recover the defective set with high probability up to a critical noise level, beyond which errors become unavoidable. Techniques from noisy binary group testing also provide useful insights. For example, Price et al. [ 14 ] developed fast splitting algorithms that achieve near-optimal test complexity and runtime under stochastic test errors, although their analysis focuses on Boolean outcomes. 1.4 Other Noise Models Beyond the mentioned models, a few works have explored adversarial or structured corruption models. In particular, Li and Wang [ 12 ] studied combinatorial QGT under bounded adversarial noise, where test outcomes may be perturbed arbitrarily within fixed limits. In this setting, exact recovery is generally impossible, and the goal shifts to partial recovery. They established lower bounds on the order of \Omega(n\log n) tests and proposed deterministic test designs with efficient decoding that achieve these bounds up to constant factors. 1.5 Our Contributions Table 1 compares our results with existing work. Our main contributions are summarized as follows: • We provide a unified analysis of three quantitative group testing models—noiseless, additive Gaussian noise, and noisy Z-channel—under a common non-adaptive random design framework. This contrasts with prior work, which typically focuses on individual noise models or specific problem formulations. • We provide both achievability and converse bounds for the two noisy models. In particular, for the additive Gaussian noise model, we establish matching achievability and converse bounds on the number of tests required for exact recovery. To the best of our knowledge, this yields the first tight characterization of the sample complexity for Gaussian QGT up to constant factors. • We analyze two decoding approaches across all models: a computationally efficient correlation-based linear estimator and a statistically optimal (but generally combinatorial) least squares estimator (LSE). This allows us to explicitly quantify the performance gap between polynomial-time algorithms and information-theoretically optimal decoding under different noise regimes. • While simple correlation-based linear estimators for quantitative group testing were previously studied in both the noiseless setting [ 4 ] and noisy settings [ 6 ] , our results provide sharper guarantees. In particular, prior formulations allow multi-set defectives within pooled tests, whereas we restrict attention to standard binary testing matrices, aligning more closely with the classical definition of QGT. Despite this stronger modeling restriction, our bounds achieve equal or improved sample complexity in all three models, and we derive explicit non-asymptotic guarantees with concrete absolute constants. Organization. The remainder of the paper is organized as follows. Section 2 introduces the QGT problem formulation and the three observation models considered. Section 3 presents the main results of the paper. Section 4 provides the proofs of the main theorems. Setting Decoder Required number of tests m Noiseless Linear Estimator (Theorem 1 ) \displaystyle m\geq\Bigl(\frac{16}{\ln 3}k+8-\frac{8}{\ln 3}\Bigr)\log\bigl(k(n-k)\bigr) Noiseless Hahn-Klimoroth (Linear Estimator) [ 4 ] \displaystyle m=O\left(\frac{1+\sqrt{\theta}}{1-\sqrt{\theta}}k\log\frac{n}{k}\right)=O\left((1+\sqrt{\theta})^{2}k\log n\right) Noiseless Hahn-Klimoroth and Muller (Polynomial-time) [ 5 , 7 ] \displaystyle m=(1+\delta)\frac{1+\sqrt{\theta}}{1-\sqrt{\theta}}\frac{k\log(n/k)}{\log k} Noiseless Soleymani and Javidi (Polynomial-time) [ 17 ] \displaystyle m\geq(2e+\gamma)\frac{k}{\log k}\log\frac{n}{k}\log\log k Noiseless Information-theoretic [ 2 ] \displaystyle m=\Omega\left(2\,\frac{k\log(n/k)}{\log k}\right) Additive Gaussian LSE Decoder (Theorem 2 ) \displaystyle m\geq(1+o(1))\frac{k\log(n/k)}{\log(1+k/\sigma^{2})} Additive Gaussian Information-theoretic (Theorem 2 ) \displaystyle m=\Omega\!\left(\frac{k\log(n/k)}{\log(1+k/4\sigma^{2})}\right) Additive Gaussian Linear Estimator (Theorem 2 ) \displaystyle m\geq\Bigl(\frac{16}{\ln 3}k+32\sigma^{2}+8-\frac{8}{\ln 3}\Bigr)\log(k(n-k)) Additive Gaussian Hahn-Klimroth and Kasser (Linear Estimator) [ 6 ] \displaystyle m\geq(4\gamma+\epsilon)(1+\sqrt{\theta})^{2}k\ln n Noisy Z-channel

Read the complete text