Source-linked AI summary
Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms
Chun Lam Chan, Pak Hou Che, Sidharth Jaggi, Venkatesh Saligrama
TL;DR
The paper asks how many non-adaptive group tests are needed to identify a small defective subset when measurements are noiseless or independently noisy. It proves information-theoretic lower bounds and analyzes computationally efficient CBP and COMP algorithms, obtaining explicit upper bounds and a constant-factor characterization of their gap. The analysis includes noisy-test strategies such as repetition and relaxed thresholding.
Problem
The paper addresses the lack of explicit measurement guarantees for non-adaptive group testing despite known order-optimal bounds, including the harder independently noisy setting.
Method
The paper derives information-theoretic lower bounds and analyzes computationally efficient CBP and COMP algorithms in noiseless and noisy models.
Results
The paper provides explicit upper and lower bounds on the tests needed for a target error probability, with noisy bounds incorporating q-dependent factors and algorithmic analysis.
Takeaways & Limitations
The work makes the gap between efficient algorithmic guarantees and information-theoretic requirements explicit rather than reporting only order-optimal scaling.
Abstract
from arXiv · showhide
We consider the problem of detecting a small subset of defective items from a large set via non-adaptive "random pooling" group tests. We consider both the case when the measurements are noiseless, and the case when the measurements are noisy (the outcome of each group test may be independently faulty with probability q). Order-optimal results for these scenarios are known in the literature. We give information-theoretic lower bounds on the query complexity of these problems, and provide corresponding computationally efficient algorithms that match the lower bounds up to a constant factor. To the best of our knowledge this work is the first to explicitly estimate such a constant that characterizes the gap between the upper and lower bounds for these problems.
I. INTRODUCTION
The paper studies non-adaptive group testing with small reconstruction error in noiseless and independently noisy measurement settings. It addresses the gap between known order-optimal bounds and explicit, computationally efficient measurement guarantees.
- Problem setting: Non-adaptive testing fixes every test independently of previous outcomes, enabling parallelized and automated testing.The paper notes that adaptivity improves measurement complexity by at most a constant factor in known results.
- Problem setting: Noisy measurements independently differ from their true outcomes with probability q, making defective-set estimation more challenging.The work distinguishes measurement noise from estimation errors produced by the decoding algorithm.
- Contribution: The paper requires algorithms to be computationally efficient while remaining near-optimal in the number of measurements.This contrasts with some prior approaches that optimize measurements without computational-efficiency guarantees.
- Prior bounds: T = Θ(d log(n)) tests are order-optimal in both noiseless and noisy variants, while noise introduces an additional constant factor.The noisy-case constant may depend on the noise parameter q and the allowable error probability δ.
- Contribution: The authors explicitly analyze CBP and COMP, providing upper bounds, information-theoretic lower bounds, and simulations that closely match the analysis.The resulting bounds are asymptotically independent of n and d.
II. BACKGROUND
Group testing represents items and tests with a binary matrix, producing noiseless or noisy outcomes from which the defective set is estimated. The model defines error probability over the random input, testing matrix, and noise.
- Model and notation: The goal is to identify a small defective subset D within a larger item set N using as few group tests as possible.Each test returns whether at least one defective item is included.
- Model and notation: A T × n binary matrix M assigns items to tests, with rows representing tests and columns representing items.The matrix-generation procedure is part of the group-test design.
- Model and notation: The binary vector x marks defective items, while y records noiseless outcomes and x̂ records the decoder’s estimated defective locations.A one in y indicates that the corresponding test contains at least one defective item.
- Model and notation: In the noisy model, each observed outcome differs from its noiseless counterpart independently with probability q.The noise vector ν marks the locations where the two outcome vectors differ.
- Model and notation: The algorithm’s error probability is the probability that the estimated vector differs from the input vector over x, M, and ν.This definition accounts for randomness in the defective set, test design, and measurement noise.
1. NOISELESS ALGORITHMS
The noiseless algorithms decode defective items from a random binary testing matrix, while their noisy counterparts modify or repeat tests to tolerate measurement errors. CBP uses negative tests to identify non-defectives, whereas COMP matches matrix columns to outcomes and NCOMP relaxes that match.
- Noiseless algorithms: CBP uses only negative tests to identify non-defective items and declares all remaining items defective.Its estimate is formed as 1 − m(y), where m(y) marks items appearing in at least one negative-test row.
- Noiseless algorithms: CBP errors are false positives caused when a non-defective item appears only in positive tests or is otherwise hidden by defective items.The decoder does not produce false negatives in the described noiseless setting.
- Noiseless algorithms: The random matrix for COMP uses independent entries that equal one with probability p.CBP instead samples each test’s item selections with replacement, yielding i.i.d. matrix entries.
- Noiseless algorithms: COMP declares an item defective when every one-entry position in its matrix column is also one in the result vector.A non-defective item can become a false positive when defective columns hide its distinguishing positions.
- Noisy algorithms: Noisy CBP repeats each noiseless test K times and uses majority voting before applying the noiseless CBP decoder.This repetition converts each group of K noisy outcomes into a single thresholded outcome.
- Noisy algorithms: NCOMP replaces COMP’s exact containment rule with a mismatch threshold depending on column weight and noise parameter q.It declares item i defective when |S_i| ≥ |T_i|(1−q(1+∆)).
III. MAIN RESULTS
The paper establishes information-theoretic lower bounds on tests required for group testing with noiseless and noisy measurements. Under d=o(n), these bounds scale as Ω(d log(n)), with noise increasing the requirement by a factor involving H(q).
- Lower bounds: Information-theoretic lower bounds are established for any group-testing algorithm with a specified allowable probability of error.The bounds are stated explicitly in terms of the acceptable error probability ε.
- Noiseless measurements: (1 − ϵ)d log(n/d) tests are necessary for noiseless measurements.This is the stated folklore lower bound for algorithms whose probability of error is at most ε.
- Noisy measurements: [(1 − ϵ)d log(n/d)]/(1 − H(q)) tests are necessary when measurements are independently noisy with probability q.The noisy-measurement lower bound extends the noiseless bound by the factor 1/(1 − H(q)).
- Asymptotic implication: Under the assumption d = o(n), both lower bounds are Ω(d log(n)).The assumption makes the logarithmic dependence on n explicit in the asymptotic form.
B. Upper Bounds
The paper gives explicit test-count bounds for computationally efficient CBP and COMP algorithms in noiseless and noisy group testing, comparing them with information-theoretic lower bounds. In the noisy setting, the proposed approach includes a nontrivial repeated-test construction whose bound is asymptotically worse than the lower bound, alongside the paper’s main result.
- The work explicitly computes the number of tests needed to achieve a desired error probability using computationally efficient CBP and COMP algorithms.
- 2(1 + δ)ed ln n tests suffice for CBP with error probability at most n^-δ.
- Theorem 3 and Theorem 4 bounds are commensurate with the corresponding lower bound in Theorem 2.
- The NCBP noisy-measurement construction requires 2e(1 + δ)2(ln ln n + ln d + δ ln n + 1 + ln(2(1 + δ)))(1 −2q)^-2d log(n) tests.
- The NCBP bound is asymptotically worse than the corresponding lower bound, motivating the paper’s main result.
- The corresponding noisy upper bound differs from the lower bound by at most 4.36(1 + δ)2(1 −2q)^-2, a factor depending only on q and δ.
IV. PROOF OF LOWER BOUNDS
The lower-bound proof models the input, noiseless outcomes, noisy outcomes, and estimate as a Markov chain, then applies data processing and channel-capacity arguments. For binary symmetric noise, each test contributes at most 1 − H(q) information, yielding the noisy lower bound.
- The proof uses the Markov chain X → Y → Ŷ → X̂ to relate the input, noiseless outcomes, noisy outcomes, and estimate.
- The input entropy is log |X| for uniformly distributed length-n, d-sparse vectors, and Stirling’s approximation lower-bounds it by d log(n/d).
- Data processing gives I(X; X̂) ≤ I(Y; Ŷ), bounding recoverable information through the noisy test outcomes.
- For BSC(q) noise, the total information conveyed by T tests is at most T(1 − H(q)).
- Combining these inequalities produces the information-theoretic lower bound for the number of tests.
A. Noiseless Group Testing
For noiseless group testing, the proofs analyze COMP and CBP through error-event bounds and a coupon-collector viewpoint. Optimizing the Bernoulli test probability yields explicit logarithmic test bounds with error probability at most n^-δ.
- CBP: CBP can be viewed as a coupon-collector process whose goal is to collect all non-defective items appearing in negative tests.
- The lower-bound analysis focuses on binary symmetric noise, while the information-theoretic technique also applies to more general discrete memoryless noise.
- CBP: The CBP tail analysis combines a coupon-collection bound with a Chernoff bound on the number of items in negative tests, using a design parameter ρ.
- CBP: Choosing T above the derived bound preserves the error guarantee, yielding probability of error at most n^-δ for sufficiently large n.
- COMP: The COMP proof bounds false positives, where a non-defective column is hidden by columns corresponding to defective items.
- COMP: Optimizing the test-entry probability gives p = 1/d, and setting T = βd ln n controls the false-positive probability.
- COMP: Choosing β = (1 + δ)e makes T ≥ (1 + δ)ed ln n sufficient for the required error decay.
B. Noisy Group Testing
The noisy group-testing analysis bounds errors from false negatives and false positives, then balances these constraints to obtain an explicit test-complexity constant. It also compares a repeated noiseless-CBP benchmark with noisy COMP and validates Noisy-COMP theoretically and empirically.
- Noisy CBP benchmark: Repeating each noisy test K times provides a benchmark based on noiseless CBP, with K chosen so the error probability decays asymptotically in n.The analysis applies Chernoff and union bounds to determine a sufficient repetition level.
- Noisy CBP benchmark: False negatives require β− to exceed a bound determined by q, the threshold parameter ∆, and the growth of d relative to n.The requirement is that the false-negative probability be at most n^-δ.
- Noisy COMP analysis: False positives arise from ordinary column masking and additional noise-induced masking, yielding an explicit lower bound β+.The bound depends on α, q, ∆, δ, and the asymptotic relation d=o(n).
- Noisy COMP analysis: The overall constant β must satisfy β ≥ max{β−, β+}, so both false-negative and false-positive constraints hold.The threshold ∆ trades off the two error types: smaller ∆ increases false negatives, whereas larger ∆ increases false positives.
- Parameter optimization: Balancing the two constraints gives an optimal threshold ∆*, and optimizing the resulting expression places the minimum at α = 0.5.The balance is obtained by equating the bounds and substituting the resulting parameter values into the explicit expression for β.
- Empirical validation: Figure 5 examines Noisy-COMP success probability versus the number of tests T across different noise parameters q.The authors report that simulations correlate well with the corresponding theoretical bounds.
A. Noisy Random Incidence Algorithm
Simulations examine Noisy-COMP's probability of error as the number of tests varies. The reported experimental values correlate well with the corresponding theoretical bounds.
- Empirical validation: Simulations evaluate Noisy-COMP error probability as a function of the number of tests.The paper presents Figure 5 as the space-limited experimental validation.
- Empirical validation: The experimental values correlate well with the corresponding theoretical bounds.