The Noisy Quantitative Group Testing Problem

Arya Mazumdar; Neha Sangwan; Tenghao Li; Xiaxin Li

arxiv: 2601.11797 · v2 · submitted 2026-01-16 · 💻 cs.IT · math.IT

The Noisy Quantitative Group Testing Problem

Tenghao Li , Neha Sangwan , Xiaxin Li , Arya Mazumdar This is my paper

Pith reviewed 2026-05-16 12:52 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords quantitative group testingadditive Gaussian noiseexact recoveryinformation theoretic boundsleast squares estimatorsparse recovery

0 comments

The pith

In quantitative group testing with additive Gaussian noise, lower and upper bounds on the number of tests match in order for exact recovery.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper studies quantitative group testing, where each test returns the exact count of defectives inside the tested pool, under three models: noiseless, additive Gaussian noise, and Z-channel noise. It analyzes a correlation-based linear estimator and a least-squares estimator, deriving upper bounds on the number of tests needed for exact recovery of a sparse defective set with high probability, and pairing them with information-theoretic lower bounds. The central result is that the bounds coincide in order under additive Gaussian noise. A reader would care because this determines the minimal measurement budget for reliable count-based pooled testing when noise is present, which arises in applications such as sensor networks or pooled biological assays.

Core claim

In the additive Gaussian noise model for quantitative group testing, the information-theoretic lower bound and the algorithmic upper bounds achieved by the correlation-score linear estimator and the least-squares estimator match in order, so the number of tests required for exact recovery of k defectives out of n items scales the same way from both sides.

What carries the argument

The correlation-score linear estimator and the least-squares estimator applied to quantitative (count-valued) measurements, which together achieve the order-matching upper bounds under additive Gaussian noise.

If this is right

Upper bounds on the number of tests sufficient for exact recovery with vanishing error probability in the noiseless, Gaussian, and Z-channel models.
Matching information-theoretic lower bounds that apply to any recovery procedure.
In the additive Gaussian case the upper and lower bounds agree in order, establishing order optimality of the estimators.
The same style of analysis yields concrete bounds for the Z-channel noise model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Quantitative testing may need substantially fewer measurements than binary group testing once noise is present, because each test returns more information.
The order-optimal scaling could be used to set pool sizes in practical count-based sensing systems where additive noise dominates.
Extending the same estimators to other count-valued noise models would test whether order matching holds more generally.

Load-bearing premise

The additive Gaussian and Z-channel noise models correctly describe the measurement errors, and the estimators succeed in exact recovery whenever the number of tests meets the derived bounds.

What would settle it

An explicit calculation or simulation for large n and k showing that exact recovery in the Gaussian-noise model requires asymptotically more tests than the stated upper bound (or fewer than the lower bound) would disprove the order-matching claim.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives order-matching upper and lower bounds for exact recovery in noisy quantitative group testing under Gaussian noise using correlation and least-squares estimators.

read the letter

The main point is that they extend quantitative group testing to noisy settings and show that, for additive Gaussian noise, the information-theoretic lower bound on the number of tests matches the upper bounds achieved by a linear correlation estimator and a least-squares estimator, both in order, for exact recovery with high probability under standard sparsity regimes. They also treat the noiseless case and a Z-channel noise model, deriving upper bounds via the same two algorithms plus lower bounds where possible. The work sits squarely in the combinatorial search and information theory literature, building directly on prior noiseless QGT results by adding explicit noise models and estimators that achieve the scaling. The derivations rely on standard mutual information arguments and estimation theory rather than any self-referential fitting, which keeps the circularity burden low. The Gaussian case is the cleanest part, with the order match holding across the relevant k, n, and noise variance ranges. The Z-channel analysis is more one-sided, with only upper bounds shown, but that is a minor gap rather than a flaw in the central claim. Assumptions about the noise models are stated up front and are typical for this subfield; they do not appear to hide any load-bearing issues that would invalidate the asymptotics. This is the kind of paper that is useful for people already working on group testing variants who need concrete noisy extensions with matching bounds. It is not reshaping the broader field, but the results look reproducible from the described methods and the analysis holds together. I would send it to peer review without hesitation; the matching bounds in the Gaussian setting are worth referee scrutiny even if some details need tightening.

Referee Report

2 major / 2 minor

Summary. The paper studies quantitative group testing (QGT) under noiseless, additive Gaussian noise, and noisy Z-channel models. It analyzes two estimators (linear correlation scores and least-squares) and derives upper bounds on the number of tests needed for exact recovery with vanishing error probability, complemented by information-theoretic lower bounds. The central claim is that, in the additive Gaussian noise setting, the lower and upper bounds match in order.

Significance. If the order-matching result holds under the stated sparsity and noise regimes, the work provides fundamental scaling laws for noisy QGT that connect algorithmic achievability (via correlation and LSE estimators) to information-theoretic converses. This is useful for sparse recovery applications where quantitative measurements are subject to additive or binary noise, and the explicit treatment of multiple noise models strengthens the contribution relative to prior noiseless QGT analyses.

major comments (2)

[Section on information-theoretic lower bounds (Gaussian case)] The information-theoretic lower bound derivation for the Gaussian noise model (appearing after the algorithmic upper bounds) is summarized at a high level but lacks the explicit mutual-information or Fano-type steps needed to confirm the precise scaling with noise variance; without these steps it is not possible to verify that the lower bound indeed matches the upper bound beyond big-O notation.
[LSE analysis for Gaussian noise] The upper bound for the least-squares estimator in the additive Gaussian model assumes the noise variance is known exactly when forming the estimator; the paper does not address how the bound degrades under variance estimation error or provide a data-driven variant, which is load-bearing for the exact-recovery claim under realistic conditions.

minor comments (2)

[Introduction and model definitions] Notation for the sparsity parameter k and the number of tests m is introduced without a consolidated table of symbols, making it easy to confuse the regimes across the three noise models.
[Abstract] The abstract states that bounds 'match in order' for the Gaussian case but does not display the explicit leading-term expressions; adding these (even in a remark) would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. The comments highlight opportunities to strengthen the presentation of the lower bounds and to clarify the assumptions in the LSE analysis. We address each point below and indicate the revisions we will make.

read point-by-point responses

Referee: The information-theoretic lower bound derivation for the Gaussian noise model (appearing after the algorithmic upper bounds) is summarized at a high level but lacks the explicit mutual-information or Fano-type steps needed to confirm the precise scaling with noise variance; without these steps it is not possible to verify that the lower bound indeed matches the upper bound beyond big-O notation.

Authors: We agree that the lower-bound section would benefit from greater explicitness. In the revision we will insert the full derivation: we compute the mutual information I(Y; S) between the vector of noisy quantitative measurements and the unknown support S, apply Fano’s inequality to bound the error probability, and explicitly track the dependence on the noise variance σ². This will show that the resulting lower bound on the number of tests matches the upper bound in order (including the precise scaling with σ²), rather than only in big-O notation. revision: yes
Referee: The upper bound for the least-squares estimator in the additive Gaussian model assumes the noise variance is known exactly when forming the estimator; the paper does not address how the bound degrades under variance estimation error or provide a data-driven variant, which is load-bearing for the exact-recovery claim under realistic conditions.

Authors: The analysis is stated under the standard modeling assumption that σ² is known. We acknowledge that this assumption should be discussed. In the revised manuscript we will add a short subsection (or remark) showing that a consistent estimator of σ² can be formed from the LSE residuals (or from a small number of additional calibration measurements) and that, in the sparsity and noise regimes considered, the plug-in estimator yields the same order of the number of tests for exact recovery with high probability. We will also note that the constants in the bound may degrade by a small factor but the scaling remains unchanged. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bounds derived independently via standard information theory

full rationale

The paper derives information-theoretic lower bounds (via standard converse arguments such as Fano or mutual information) and algorithmic upper bounds (via explicit analysis of linear correlation and least-squares estimators) for exact recovery in quantitative group testing under noiseless, Gaussian, and Z-channel models. The order-matching claim for additive Gaussian noise follows from these separate derivations aligning asymptotically in the stated sparsity and noise regimes, without any reduction of a 'prediction' to a fitted input by construction, self-definitional parameters, or load-bearing self-citations. The central results rest on external mathematical tools (concentration inequalities, estimation theory) that are not redefined in terms of the target bounds. This is the common honest outcome for information-theoretic papers whose analysis is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard definitions of the three noise models and asymptotic regimes for exact recovery; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Additive Gaussian noise and noisy Z-channel models accurately capture measurement errors in quantitative group testing
Invoked when stating the models and deriving bounds for each.

pith-pipeline@v0.9.0 · 5386 in / 1018 out tokens · 35790 ms · 2026-05-16T12:52:29.161061+00:00 · methodology

The Noisy Quantitative Group Testing Problem

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)