PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-adaptive Group Testing: Explicit bounds and novel algorithms

Chun Lam Chan, Sidharth Jaggi, Venkatesh Saligrama, Samar Agnihotri

arXiv:1202.0206v5cs.IT

TL;DR

The paper addresses how to identify sparse defective sets efficiently in noisy non-adaptive group testing while retaining near-optimal test counts. It analyzes three algorithm families and derives explicit finite-sample bounds, showing that their requirements match information-theoretic lower bounds within parameter-independent constant factors.

  • Problem

    Existing group-testing bounds were often asymptotic, leaving the constants governing tests needed for a fixed error probability insufficiently explicit.

  • Method

    The paper analyzes CoCo, CoMa, and LP decoding algorithms for noiseless and noisy non-adaptive group testing using coupon-collector, column-matching, and perturbation analyses.

  • Results

    The algorithms achieve sample complexity within an explicitly computable constant factor of information-theoretic lower bounds, with explicit dependence on noise, error probability, n, and d or its upper bound.

  • Takeaways & Limitations

    Computationally efficient algorithms can provide near-optimal non-adaptive group testing under noiseless, symmetric-noise, asymmetric-noise, and activation-noise settings.

Abstract

from arXiv · show

We consider some computationally efficient and provably correct algorithms with near-optimal sample-complexity for the problem of noisy non-adaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be "sparse". We consider non-adaptive randomly pooling measurements, where pools are selected randomly and independently of the test outcomes. We also consider a model where noisy measurements allow for both some false negative and some false positive test outcomes (and also allow for asymmetric noise, and activation noise). We consider three classes of algorithms for the group testing problem (we call them specifically the "Coupon Collector Algorithm", the "Column Matching Algorithms", and the "LP Decoding Algorithms" -- the last two classes of algorithms (versions of some of which had been considered before in the literature) were inspired by corresponding algorithms in the Compressive Sensing literature. The second and third of these algorithms have several flavours, dealing separately with the noiseless and noisy measurement scenarios. Our contribution is novel analysis to derive explicit sample-complexity bounds -- with all constants expressly computed -- for these algorithms as a function of the desired error probability; the noise parameters; the number of items; and the size of the defective set (or an upper bound on it). We also compare the bounds to information-theoretic lower bounds for sample complexity based on Fano's inequality and show that the upper and lower bounds are equal up to an explicitly computable universal constant factor (independent of problem parameters).

I. INTRODUCTION

The paper develops computationally efficient algorithms for noisy and noiseless non-adaptive group testing, where random pools identify sparse defective sets despite measurement noise. It derives explicit finite-sample bounds and shows these algorithms approach information-theoretic limits within constant factors.

  • Problem setting: Non-adaptive testing fixes each pool independently of previous outcomes, enabling parallelized and automated testing but imposing greater simplicity than adaptive procedures.The objective is to identify a small defective subset using substantially fewer than n tests.
  • Problem setting: The paper studies noisy tests with independent false positives and false negatives, while also addressing asymmetric and activation noise models.Its primary analysis uses symmetric noise for tractability, with extensions to other models for LP decoding.
  • Algorithms: Three algorithmic families are analyzed: Coupon Collector (CoCo), Column Matching (CoMa), and LP decoding algorithms related to compressive sensing.CoCo connects group testing to coupon collection; CoMa uses iterative column matching; LP methods use perturbation analysis for nonlinear Boolean measurements.
  • Main results: The algorithms achieve near-optimal sample complexity, matching information-theoretic lower bounds within a constant factor independent of n and d.The bounds retain this comparison across the studied noiseless and noisy settings.
  • Explicit guarantees: The analysis makes test-complexity guarantees explicit as functions of the target error probability, noise, item count, and defective-set size or upper bound.The paper emphasizes finite-parameter constants rather than only asymptotic order statements.
  • Main results: Several methods require only an upper bound D on the number of defectives, rather than the exact defective count d.The stated exception is the LP-based algorithms, for which universal versions were still ongoing research.

II. BACKGROUND

The paper formulates non-adaptive group testing through a binary item vector, randomized test matrix, noiseless or noisy outcomes, and decoding algorithms influenced by compressive sensing.

  • Model and notation: A binary vector x marks the unknown defective subset D within n items, whose size is d.The support of x identifies defective items; non-defective items correspond to zero entries.
  • Model and notation: Each row of the T × n matrix M defines a test, while each column represents an item included wherever it contains a 1.The test-generation procedure and estimation of D jointly define the group-testing design.
  • Model and notation: In the noiseless model, an outcome is 1 exactly when the corresponding test contains at least one defective item.The noiseless result vector y therefore records whether each pool intersects D.
  • Noise models: In the noisy model, each observed outcome differs from its noiseless counterpart independently with probability q, producing false-positive and false-negative tests.The paper also briefly considers asymmetric bit-flip and activation-noise models.
  • Compressive-sensing background: The paper targets computationally efficient support recovery using column-matching and LP-inspired decoders, motivated by compressive-sensing methods.The cited background introduces OMP and Basis Pursuit as the corresponding compressive-sensing inspirations.

2) Basis Pursuit:

Basis Pursuit relaxes the sparse-recovery problem into convex optimization, while the surrounding setup motivates row-based group-testing decoders with randomized test matrices.

  • Basis Pursuit: Basis Pursuit relaxes the non-linear sparsity constraint into a convex optimization problem.This provides a compressive-sensing analogue for the LP-based group-testing methods discussed later.
  • Basis Pursuit: With T = c4d log(n), Basis Pursuit achieves ||x* − x||2 ≤ c6||z||2 with probability at least 1 − 2c5n.The guarantee is stated for constants c4, c5, and c6 under the cited compressive-sensing model.
  • Group-testing algorithms: The paper introduces three algorithm classes, with the latter two analyzed in both noiseless and noisy settings.Their performance is stated separately from the corresponding proofs.
  • Row-based construction: A row-based decoder constructs each test by sampling g items with replacement and setting matrix entries to 1 for sampled items.The resulting matrix uses rows as independently generated test pools under this construction.
  • Row-based decoding: The decoder uses only negative tests to identify non-defective items, declaring all remaining items defective.A non-defective item is recovered when it appears in at least one negative test.

2) “Column Matching” Algorithms:

Column Matching decoders compare matrix columns with observed outcomes: exact containment handles noiseless tests, while thresholded matching accommodates noise and mismatches.

  • CoMa: CoMa generates each matrix entry independently, setting it to 1 with probability p and to 0 otherwise.The group-sampling parameter p and test count T are design parameters.
  • CoMa: The noiseless CoMa decoder declares item j defective when every 1 in column j aligns with a 1 in the result vector.All other items are declared non-defective.
  • CoMa: CoMa produces no false non-defective estimates, but non-defective items can be falsely declared defective when defective columns hide them.This masking occurs when other defective columns cover every 1-location of a non-defective column.
  • No-CoMa: Noise can create both false non-defective and false defective estimates by reducing matches or pushing non-defective columns above the threshold.The figure example attributes a false non-defective decision to noisy mismatches and a false defective decision to measurement errors.
  • No-CoMa: No-CoMa replaces exact containment with a mismatch threshold determined by column weight and the noise parameter q.The decoder therefore relaxes the sharp threshold used by noiseless CoMa.
  • No-CoMa: No-CoMa declares item j defective when |S_j| ≥ |T_j|(1 − q(1 + τ)); otherwise it declares the item non-defective.T_j records 1-locations in the column, while S_j records locations where both the column and noisy outcome equal 1.

3) LP-decoding Algorithms:

The LP-decoding class adapts compressive-sensing relaxations to Boolean group-testing measurements by combining relaxed item variables with error-accounting slack variables.

  • LP construction: LP decoding uses a randomly generated T × n matrix whose entries equal 1 independently with probability p = 1/D.Here D is the available upper bound on the number of defectives.
  • LP formulation: The No-LiPo formulation uses relaxed x variables and error slack variables to represent noisy Boolean measurements within a linear program.The paper presents this construction as a linear relaxation of group testing inspired by compressive sensing.
  • No-LiPo: No-LiPo relaxes each x_i to 0 ≤ x_i ≤ 1, linearizes the non-linear measurements, and introduces slack variables η_i for test errors.A slack variable is zero for a correct test and positive, at least 1, for an incorrect test.
  • No-LiPo: The No-LiPo decoder minimizes the LP over (x̂, η̂) while assuming the exact defective count d is known.Its objective implements a minimum-error-vector principle through the LP formulation.
  • LiPo: LiPo is the noiseless special case of No-LiPo obtained by setting every η_i to zero.It then searches for any feasible point satisfying the resulting constraints.

D. Lower bounds on the number of tests required

The paper reprises information-theoretic lower bounds on the number of tests needed for reliable group testing, extending them from noiseless to noisy measurements. Under D=o(n), these bounds are Ω(D log(n)).

  • Information-theoretic lower bounds quantify the minimum tests required by group-testing algorithms achieving error probability at most ϵ.The paper restates these bounds to benchmark its algorithmic upper bounds.
  • Noisy measurements admit corresponding information-theoretic lower bounds for algorithms with error probability at most ϵ.
  • D=o(n) implies that the noiseless and noisy lower bounds are Ω(D log(n)).

III. MAIN RESULTS

The paper uses binary logarithms by default and defines Γ as the ratio of the natural logarithms of D and n. The binary entropy function H(.) is used in the lower-bound expressions.

  • All logarithms are binary unless explicitly identified otherwise, with natural logarithms written as ln(.).
  • Γ is defined as ln(D)/ln(n).
  • H(.) denotes the binary entropy function.

A. Upper Bounds on the number of tests required

The paper derives explicit test-complexity bounds for computationally efficient Coupon Collector, column matching, and LP-decoding algorithms. These achievability bounds match information-theoretic lower bounds within explicitly computable constant factors, including under several noise models.

  • Main contributions: The analysis explicitly computes the tests needed for a desired error probability, improving beyond order-of-magnitude estimates.The paper presents novel coupon-collector and perturbation analyses, alongside tighter analyses for column matching algorithms.
  • Coupon Collector algorithm: The CoCo algorithm uses its novel connection to the Coupon Collector’s problem to require no more than 2eD(1 + δ) ln(n) tests.
  • Column matching algorithms: The CoMa algorithm requires no more than eD(1 + δ) ln(n) tests for error probability at most n^-δ.
  • Column matching algorithms: No-CoMa extends column matching to noisy observations through a thresholded scheme with parameters depending on q, δ, and Γ.The supplied passage introduces γ and internal parameters τ and p for the remaining algorithms, while the displayed test bound is incomplete.
  • LP-decoding algorithms: No-LiPo provides LP-based decoding for the main noisy measurement scenario and is also robust to asymmetric noise.The paper gives separate explicit bounds for asymmetric and activation noise models.
  • Limitations: The LP-based constants are not optimized, although they demonstrate functional dependence on δ and q.
  • Comparison with lower bounds: The LP-based achievability schemes match information-theoretic lower bounds up to a finite, explicitly computable constant factor.One stated gap is at most 12.83(1+√γ)^2(1+δ)(1−2q)^−2 for a corresponding noisy bound.

A. Coupon collector algorithm

The Coupon Collector algorithm views items appearing in negative tests as coupon draws and chooses the pool size to optimize the resulting stopping-time bound. Tail-bound analysis converts the expectation into explicit high-probability guarantees.

  • A. Coupon collector algorithm: The analysis models items in CoCo test vectors as uniformly and independently sampled coupons across tests.Repeated items are allowed, and the test-vector representation has a natural correspondence with the group-testing procedure.
  • A. Coupon collector algorithm: Optimizing the expected negative-test coverage gives pool size g = 1/ln(n/(n−D)) and asymptotically requires T ≥ eD ln n tests.D is an upper bound on the unknown defective-set size d, with D = o(n).
  • A. Coupon collector algorithm: The expectation-based bound alone is insufficient for an error probability decaying as n^−δ, so the analysis adds a corresponding tail bound.The expected relation must be modified to control the probability that the stopping condition has not been reached.
  • A. Coupon collector algorithm: The tail analysis combines a coupon-collector stopping-time bound with a Chernoff bound on the number of items appearing in negative tests.The right-hand side controls uncollected coupon types, while the left-hand side controls deviations below expected negative-test coverage.
  • A. Coupon collector algorithm: For sufficiently large n, choosing the derived test bound yields error probability at most n^−δ.The proof obtains this by union bounding the relevant low-probability events and selecting T above the explicit bound.

B. Column Matching algorithms

Column Matching algorithms identify defective columns by testing whether their observed ones can be masked by defective columns or noise. The analysis derives explicit conditions balancing false-negative and false-positive errors.

  • B. Column Matching algorithms: CoMa and No-CoMa handle noiseless and noisy observations, respectively, with errors arising when non-defective columns are hidden by defective columns.In No-CoMa, noise adds a second masking mechanism for ones in non-defective columns.
  • B. Column Matching algorithms: Choosing p = 1/D and T = βD log n supports the noisy analysis when only an upper bound D on d is known.The same parameterization is used to control both false non-defective and false defective estimates.
  • B. Column Matching algorithms: The noiseless CoMa algorithm achieves error probability at most n^−δ when T ≥ (1 + δ)eD ln n.This follows after substituting p = 1/D and choosing β = (1 + δ)e.
  • B. Column Matching algorithms: The noisy algorithm requires separate bounds for false non-defective and false defective estimates, with β chosen at least as large as max{β−, β+}.The two quantities bound the respective error events and are made independent of the unknown d by replacing it with D.
  • B. Column Matching algorithms: The threshold parameter τ trades off false negatives against false defective estimates, while also needing to satisfy the Chernoff-bound condition 1 − q(1 + τ) > a.A higher threshold corresponds to smaller τ and increases false negatives; a lower threshold increases false defective estimates.
  • B. Column Matching algorithms: The noisy bound is obtained by selecting γ and τ to balance the competing error constraints before substituting them into the explicit β expression.The derivation equates the two relevant right-hand sides to determine the optimal τ.

C. LP-decoding algorithms

LP-decoding algorithms relax Boolean group-testing constraints into linear programs and analyze their objective under structured perturbations. The proof establishes unique recovery through expected cost increases and concentration.

  • C. LP-decoding algorithms: The LP-based results begin with a main theorem and derive additional noisy and model-specific guarantees as direct corollaries.The framework covers the No-LiPo- algorithm and its extensions.
  • C. LP-decoding algorithms: For known d, every feasible vector can be represented as the true x plus a non-negative combination of finite mass-conserving perturbation vectors.Each basic perturbation moves mass from a defective coordinate to a non-defective coordinate without changing total weight.
  • C. LP-decoding algorithms: The proof uses convexity to extend the perturbation analysis from individual directions to feasible convex combinations.This connects the finite perturbation characterization to the full feasible set of the linear program.
  • C. LP-decoding algorithms: The expected objective-value perturbation is Tp(1 − p)^d(1 − 2q), while the expected number of perturbed variables is Tp.These expectations quantify the average separation between the true vector and feasible perturbations.
  • C. LP-decoding algorithms: Concentration inequalities and a union bound over perturbation directions show that No-LiPo- has the unique optimum x with probability at least 1 − n^−δ.The required number of tests is T = βLP D log(n), with βLP specified by the theorem.
  • C. LP-decoding algorithms: The No-LiPo- analysis also yields order-optimal performance under the stated alternative noise model.The corresponding equations change, but the proof is essentially the same as for Binary Symmetric Channel noise.

APPENDIX

The appendix develops information-theoretic lower bounds for noisy group testing using a Markov-chain and data-processing argument. For Binary Symmetric Channel noise, each test contributes at most 1 − H(q) information units.

  • APPENDIX: The lower-bound proof models the input, noiseless outcomes, noisy outcomes, and estimate as the Markov chain X → Y → Ŷ → X̂.The data-processing inequality then bounds information available to the estimate through the noisy measurements.
  • APPENDIX: Taking X uniformly over D-sparse vectors gives its entropy as the logarithm of the size of the hypothesis class.The appendix uses this entropy as the amount of information required for identification.
  • APPENDIX: Under BSC(q) noise, the mutual information supplied by T tests is at most T(1 − H(q)).The bound uses memoryless measurement noise and standard entropy arguments.
  • APPENDIX: The same information-theoretic technique extends to more general discrete memoryless noise, including the asymmetric model considered in the paper.The appendix focuses on BSC(q) for presentation.
  • APPENDIX: Stirling’s approximation lower-bounds the hypothesis entropy by D log(n/D), which is then substituted into the final sample-complexity lower bound.This connects the information requirement to the number of items and the defective-set upper bound.
Loading 1202.0206v5…