PaperlayerView exact revision on arXiv

Source-linked AI summary

Group testing algorithms: bounds and simulations

Matthew Aldridge, Leonardo Baldassini, Oliver Johnson

arXiv:1306.6438v2cs.ITmath.PR

TL;DR

The paper asks how effectively noiseless non-adaptive group testing can recover sparse defective sets without adapting tests after observing outcomes. It analyzes COMP, DD, SCOMP, and SSS using rate bounds and simulations under Bernoulli designs. DD outperforms COMP and is essentially optimal in denser regimes, while SCOMP performs close to SSS in simulations.

  • Problem

    The paper studies how to detect defective items efficiently in noiseless non-adaptive group testing, where tests are designed before being carried out.

  • Method

    The paper analyzes COMP, DD, SCOMP, and SSS through maximal-rate bounds across sparsity regimes and direct simulations, focusing on Bernoulli designs.

  • Results

    DD achieves higher rates than COMP, matches SSS in denser regimes, and SCOMP performs very close to SSS in simulations.

  • Takeaways & Limitations

    DD is asymptotically essentially optimal in some denser regimes, while SCOMP provides practical performance close to the optimal but difficult SSS algorithm.

  • Takeaways & Limitations

    For denser regimes, SSS under Bernoulli designs falls below rate 1, possibly reflecting suboptimal designs or an adaptivity gap.

Abstract

from arXiv · show

We consider the problem of non-adaptive 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. By considering the asymptotic rate of these algorithms with Bernoulli designs we see that DD outperforms COMP, that DD is essentially optimal in regimes where $K \geq \sqrt N$, and that no algorithm with a nonadaptive Bernoulli design can perform as well as the best non-random adaptive designs 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$.

1 Introduction

The paper studies noiseless non-adaptive group testing through four detection algorithms, emphasizing Bernoulli designs and comparisons with existing combinatorial and adaptive approaches. DD improves on COMP in rate bounds, while SCOMP performs close to SSS in simulations, especially for denser problems.

  • Testing designs: Bernoulli random designs avoid requiring precise knowledge of the number of defectives or the total number of tests.Each item is independently included in each test with probability p.
  • Algorithms: The paper studies four detection algorithms: COMP, DD, SCOMP, and the computationally difficult SSS benchmark.DD and SCOMP are new algorithms; SSS is included as a best-possible comparison despite limited feasibility for large problems.
  • Theoretical results: DD achieves higher maximal rates than COMP in all sparsity regimes except the fixed-K regime, where they perform equally.The comparison concerns asymptotic rate bounds for Bernoulli tests.
  • Theoretical results: DD performs as well as SSS in denser regimes, making it asymptotically essentially optimal there.The supplied passage identifies this regime as K ≥ √N.
  • Theoretical results: For K > N^0.35, even SSS falls short of nonrandom adaptive testing, suggesting suboptimal Bernoulli designs or an adaptivity gap.The paper presents both explanations as possibilities rather than resolving between them.
  • Simulations: Simulations show that DD greatly outperforms COMP, while SCOMP performs better still and comes close to SSS.The comparison is especially favorable to SCOMP in cases with larger K.

2 Definitions and notations

This section formalizes test designs, noiseless outcomes, detection algorithms, satisfying sets, sparsity regimes, and achievable rates. It also contrasts restrictive combinatorial designs with Bernoulli testing and notes limits of non-adaptive performance in denser regimes.

  • Core definitions: A testing matrix X records which of N items are included in each of T tests, with x_it = 1 indicating inclusion.This matrix represents the design stage of group testing.
  • Core definitions: A Bernoulli(p) design includes each item in each test independently with probability p.The resulting testing matrix is random across both items and tests.
  • Design properties: Disjunctness and separability provide certainty-oriented design properties but can be restrictive and may require prior knowledge of K or a test budget.The paper notes that such designs do not meet information-theoretic bounds such as the stated capacity result.
  • Core definitions: A noiseless test is positive when at least one defective item is included and negative when no defective item is included.The complete outcome vector is y ∈ {0,1}^T.
  • Core definitions: A detection algorithm maps the test-outcome vector to an estimated subset of items, while a satisfying set reproduces the observed outcomes under the design.The true defective set is itself a satisfying set.
  • Sparsity and rates: The paper parameterizes sparsity by K = N^(1−β), where larger β denotes sparser problems and smaller β denotes denser problems.The analysis assumes rare defectivity, K ≪ N.
  • Sparsity and rates: Algorithmic performance is summarized by rate, interpreted as bits learned per test, across β ∈ (0, 1].Capacity C(β) is the maximum rate achievable by any group testing algorithm.
  • Sparsity and rates: Adaptive testing achieves capacity C(β) = 1, whereas SSS has rate below 1 for β < 0.65 under the considered setting.The paper leaves open whether the gap reflects suboptimal Bernoulli designs or an adaptivity gap.

3 Algorithms

The paper presents COMP, DD, SCOMP, and SSS as detection algorithms for noiseless non-adaptive group testing, with progressively stronger evidence or optimality guarantees. COMP identifies possible defectives, DD isolates definite defectives, SCOMP greedily completes DD to a satisfying set, and SSS provides an essentially optimal but computationally difficult benchmark.

  • COMP algorithm: COMP declares every item not appearing in a negative test possibly defective, producing the largest satisfying set and only false-positive errors.Its estimate contains the true defective set, so COMP cannot miss a defective item but may retain intruding non-defectives.
  • COMP algorithm: K-disjunct designs guarantee COMP recovery, although this property is more restrictive than the condition COMP needs for the true defective set.K-disjunctness requires constraints over all item sets of size at most K, whereas COMP can succeed when the relevant condition holds only for the actual defective set.
  • DD algorithm: DD declares an item defective when it is the sole possible defective in a positive test, then labels all remaining items non-defective.Its first two steps make no mistakes; errors arise only when masked defectives are incorrectly declared non-defective, so DD makes false negatives but no false positives.
  • DD algorithm: Unlike COMP, DD can succeed despite intruding non-defectives because it may recover correctly even when the number of intruders G is positive.COMP succeeds if and only if G = 0, whereas DD can tolerate positive G.
  • SCOMP algorithm: SCOMP greedily extends DD by repeatedly selecting possible defectives that explain the most unexplained positive tests, producing a satisfying set.This procedure uses updated information after each selected item and addresses the possibility that DD itself is not a satisfying set.

4 Bounds on rates

The paper derives rate bounds for COMP, DD, and SSS under Bernoulli test designs, comparing them with an information bound. DD improves on COMP and matches SSS in a substantial sparsity regime, while SCOMP is harder to analyze but performs better in simulations.

  • The section presents bounds on the maximal achievable rates of the algorithms for Bernoulli test designs, illustrated in Figure 2.
  • The information bound provides a capacity benchmark for the achievable-rate results.It is obtained from a simple counting argument.
  • COMP has rate lower bound COMP ≥ β/(e ln 2) ≈ 0.53β under a Bernoulli(1/K) test design.
  • DD's performance guarantees strictly exceed COMP's for 0 < β < 1.The DD rate bound is derived from an exact error-probability expression, an approximation, and a conversion to a rate bound.
  • DD achieves the same rate as SSS for β ≤ 1/2, making it essentially optimal in this regime.SSS is treated as the limit of what may be possible with Bernoulli test designs because it is essentially optimal for Bernoulli tests.
  • SSS remains bounded away from the information bound achievable with adaptive testing, leaving Bernoulli suboptimality or an adaptivity gap as possible explanations.The paper also notes that SCOMP is difficult to analyze mathematically, although simulations show it performs better than DD.

5 Simulations

Simulations compare the algorithms and theoretical bounds under Bernoulli designs, showing that DD substantially improves on COMP and that SCOMP approaches SSS, especially at high success probabilities and larger K.

  • Simulation setup: 1000 simulations per plotted point evaluate Bernoulli designs with N = 500, usually K = 10 and p = 1/K.Figure 5 uses separate sparse and dense settings.
  • Algorithm comparison: DD far outperforms COMP, while SCOMP performs better still and comes very close to the computationally difficult SSS algorithm.The SCOMP–SSS performance gap is particularly small in the high success probability regime.
  • DD bounds: DD follows its analytical prediction, and its success-probability bound is reasonably tight, especially at high success probabilities.The DD bound substantially improves on the earlier COMP bound, although it remains far from the information-theoretic bound.
  • Sparse and dense cases: In the sparse case, the SSS upper bound is generally loose relative to the information bound, whereas its lower bound is generally accurate near high success rates.Here, SCOMP slightly underperforms SSS.
  • Sparse and dense cases: In the dense case, the SSS upper bound is much tighter than the information bound, while the lower bound is loose away from the high success-rate regime.The dense setting has K = 25 and βeff = 0.4820, whereas the sparse setting has K = 4 and βeff = 0.7769.

6 Conclusions and further work

The paper introduces DD and SCOMP and finds through rate bounds and simulations that they perform well, with asymptotic optimality in some denser regimes. Several analytical and design extensions remain open.

  • Conclusions: DD and SCOMP are new noiseless non-adaptive group-testing algorithms that perform well against known algorithms by both rate bounds and direct simulation.The paper reports asymptotic optimality for these methods in some denser cases.
  • Further work: Asymptotic bounds for SSS remain a future problem because they require more detailed combinatorial analysis.Such bounds would enable tighter estimates of C(β) for β > 1/2.
  • Further work: Comparing Bernoulli designs with other matrix designs, including LDPC-inspired designs, is left for future work.
  • Further work: Developing analogous algorithms and bounds for noisy group testing is also identified as future work.

A Proofs: bounds on error probability

This appendix develops probability bounds for COMP and DD under Bernoulli designs, deriving an exact DD success expression and then simpler lower bounds through conditioning and distributional analysis.

  • Reference bounds: The information-theoretic success bound and the earlier COMP bound provide reference points for analyzing Bernoulli-design algorithms.The COMP bound is maximized at p = 1/(K + 1), consistent with p = 1/K being asymptotically optimal as K grows.
  • DD exact analysis: DD succeeds exactly when every actual defective has at least one test containing it and no other possible defective.Equivalently, success is the event that L_i is nonzero for every i in K.
  • DD exact analysis: The DD analysis partitions tests according to negative tests, singleton-defective tests, multi-defective tests, and remaining tests.The variables M and L summarize these categories and possible-defective structure.
  • DD exact analysis: Conditioning successively on M, the number of intruding non-defectives G, and L yields an exact expression for DD success probability.The derivation uses multinomial distributions, conditional distributions, and independent thinning of singleton-defective tests.
  • DD bounds: The exact DD expression is a difficult triple sum, motivating simpler lower bounds obtained from Bernoulli and exponential inequalities.The resulting bound is stated for Bernoulli(p) designs and is specialized in the analysis to p = 1/K.

A.5 SSS: lower bound

The SSS analysis bounds recovery by characterizing when an alternative satisfying set produces the same outcomes as the true defective set, then controlling those alternatives with combinatorial probability bounds.

  • Result: The resulting theorem supplies a Bernoulli(p)-design upper bound on SSS success probability, while sharper asymptotic analysis remains associated with future work.
  • Alternative sets: For an alternative set L, the probability that one Bernoulli test distinguishes L from K depends on |K|, |L|, and |K ∩ L|.This follows by considering the two possible directions in which the test outcomes can differ.
  • Error event: SSS can err when the true defective set is not the unique smallest satisfying set.The analysis therefore bounds the probability that another set produces identical outcomes.
  • Combinatorial bound: A union bound over alternative satisfying sets gives an initial SSS error bound.The true defective set is excluded from the sum, producing the subtraction of one.
  • Combinatorial bound: The bound is tightened by retaining alternatives with either K − 1 shared defectives and no false positives or exactly K items.Other satisfying-set events are contained in events of these types after adding defective items.

A.6 SSS: upper bound

Theorem A.11 upper-bounds SSS success under Bernoulli designs by requiring every defective item to avoid being masked by the other defectives. This bound complements a universal bound because it depends on K rather than N, so tightness varies with sparsity.

  • A.6 SSS: upper bound: SSS serves as an idealized benchmark, so its success-probability upper bound constrains any algorithm when K is unknown.The benchmark interpretation motivates using SSS to bound algorithmic performance more generally.
  • A.6 SSS: upper bound: A masked defective prevents SSS from succeeding because the other K −1 defectives form a smaller satisfying set.The proof identifies masking as the key failure event.
  • A.6 SSS: upper bound: SSS success requires every defective i to satisfy Mi ≠ 0, yielding the stated upper-bound formulation.The successful matrices form a subset of those in which no defective is masked.
  • A.6 SSS: upper bound: Theorem A.11’s bound depends only on K, unlike the universal upper bound, so which bound is tighter depends on overall sparsity.The two bounds are complementary across sparsity regimes.

B Proofs: bounds on achievable rates

This section develops asymptotic rate bounds by normalizing binomial coefficients and contrasts the resulting COMP guarantee with the paper’s new bounds. The cited corollary gives a high-probability success guarantee for COMP at a specified test count.

  • B Proofs: bounds on achievable rates: Normalized binomial-coefficient limits support the rate calculations used for the achievable-bound analysis.The derivation takes logarithms and uses N/K = N^β.
  • B Proofs: bounds on achievable rates: The analysis contrasts the new results with Chan et al.’s lower bound derived by rearranging COMP’s success-probability bound.This establishes the comparison baseline for COMP.
  • B Proofs: bounds on achievable rates: T = e(1 + δ)K ln N tests ensures COMP has the stated success guarantee for any δ > 0.The corollary provides the required test scaling.

B.3 DD

The DD analysis proves that, under Bernoulli designs and K = N^(1−β), a test count governed by max{β, 1−β} yields success probability tending to 1. The proof controls the relevant terms using exponential bounds and concentration.

  • B.3 DD: T = (k(β) + δ)eK ln N tests makes DD’s success probability tend to 1 when K = N^(1−β), where k(β) = max{β, 1 −β}.This is the central achievable-rate result for DD.
  • B.3 DD: The proof bounds Θ(T, m0) by separating two bracketed terms over a narrow range around Tq0.The range is defined using ε := δ/6(δ+k(β)).
  • B.3 DD: Exponential inequalities and q1 = q0/(K −1) control both terms, with Np = N^β supplying the needed scaling.The bounds use inequalities such as (1−x)^y ≤ exp(−xy).
  • B.3 DD: The resulting bound Θ(T, m0) ≤ ln N(−k(β) −δ) yields vanishing error, completing the DD rate proof.The convergence to success probability 1 follows through Chernoff’s inequality and the theorem argument.

B.4 SSS

The SSS upper bound exhibits a phase transition near eK ln K tests and, combined with the COMP comparison, identifies sparsity regimes where Bernoulli non-adaptive testing may have an adaptivity gap. The gap is predicted below β* ≃ 0.653, while the universal bound dominates above it.

  • B.4 SSS: The SSS upper bound has a phase transition in the normalized number of tests needed to control φK.The analysis uses Theorem A.11 as the relevant success-probability upper bound.
  • B.4 SSS: The bound is roughly close to 1 above eK ln K tests but bounded away from 1 below eK ln K.This summarizes the two threshold regimes for φK.
  • B.4 SSS: For K = N^(1−β), COMP’s sufficient and SSS-based necessary test counts differ by β/(1−β)eK ln K for a fixed error target.The comparison uses T = e(δ+1)K ln N versus T = e(δ+1−β)K ln N.
  • B.4 SSS: Assuming SSS is optimal, Bernoulli sampling can create a strict adaptive-versus-non-adaptive capacity gap in some sparsity regimes.The paper frames this as a consequence of the SSS upper bound and Bernoulli-design rate bounds.
  • B.4 SSS: The upper-bound analysis establishes success probability at most 2/3 below the relevant threshold, so success does not tend to 1.The proof derives this by combining Theorem A.11 with the rate bounds.
  • B.4 SSS: The predicted threshold is β* = (e ln 2)/(1+e ln 2) ≃ 0.653: below it the capacity should be strictly less than 1, while above it the universal bound dominates.The less-sparse and sufficiently-sparse regimes have different controlling bounds.

C Proofs: background probability facts

This section develops multinomial-distribution facts used to analyze the DD algorithm's success probability, including marginal, conditional, and class-splitting properties. It then applies inclusion–exclusion, Bonferroni inequalities, monotonicity, and Chernoff–Hoeffding bounds to related probability expressions.

  • Concentration: The Chernoff–Hoeffding theorem supplies concentration bounds for independent identically distributed random variables.The theorem is introduced with mean EX1 = p and a parameter range 0 < ε < 1 −p.
  • Multinomial facts: The multinomial framework defines joint probabilities and provides marginal binomial distributions for individual classes.Conditional distributions remain multinomial after conditioning on one component.
  • Multinomial facts: Splitting one class independently into two subclasses preserves the multinomial form with probabilities piQ and pi(1 −Q).This property is used to transform the class-probability vector while retaining a multinomial distribution.
  • DD success probability: A symmetric multinomial case expresses the DD success probability using the φK function.The first K class probabilities are identical, with the remaining probability equal to 1 −Kq.
  • Probability bounds: Inclusion–exclusion derives the relevant identity, while Bonferroni inequalities provide lower and upper bounds by truncating the associated sum.The bounds use truncation at ℓ=1 for a lower bound and ℓ=2 for an upper bound.
  • Probability properties: The section establishes positivity of φK and states that a related function is increasing in q.The positivity follows because φK is a probability.
Loading 1306.6438v2…