PaperlayerView exact revision on arXiv

Source-linked AI summary

Novel Impossibility Results for Group-Testing

Abhishek Agarwal, Sidharth Jaggi, Arya Mazumdar

arXiv:1801.02701v3cs.ITmath.IT

TL;DR

Group testing asks how many pooled tests are needed to identify defective items, a question less explored when the number of defectives scales linearly with the item count. The paper uses Madiman-Tetali inequalities to derive stronger non-adaptive lower bounds; for a range of defect densities, these imply an adaptivity gap against known adaptive algorithms.

  • Problem

    The linear-sparsity regime d = δn is comparatively little explored, and the counting bound t ≥ nH(δ) does not provide a nontrivial converse beyond its implication that individual testing is optimal for δ > 0.5.

    Source: §1 · pp. 2–3

  • Method

    The paper applies Madiman-Tetali inequalities to exploit dependence among non-adaptive test outcomes and tighten a joint-entropy bound.

    Source: §1.1 · pp. 4–5

  • Results

    For δ ∈ (0.3471, 0.3819), known zero-error adaptive algorithms use fewer than n tests, while the best nonadaptive algorithms essentially require individual testing.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Theorem 7’s lower bound remains non-vanishingly above the counting bound, while the quantization bound also improves on it for a significant region of δ.

    Source: §3 · p. 12

    The proof uses the weak Madiman-Tetali inequalities; the authors conjecture that vanishing-error non-adaptive testing requires n − o(n) tests for every constant δ > 0.

    Source: §4 · p. 13

Abstract

from arXiv · show

In this work we prove non-trivial impossibility results for perhaps the simplest non-linear estimation problem, that of {\it Group Testing} (GT), via the recently developed Madiman-Tetali inequalities. Group Testing concerns itself with identifying a hidden set of $d$ defective items from a set of $n$ items via $t$ {disjunctive/pooled} measurements ("group tests"). We consider the linear sparsity regime, i.e. $d = \delta n$ for any constant $\delta >0$, a hitherto little-explored (though natural) regime. In a standard information-theoretic setting, where the tests are required to be non-adaptive and a small probability of reconstruction error is allowed, our lower bounds on $t$ are the {\it first} that improve over the classical counting lower bound, $t/n \geq H(\delta)$, where $H(\cdot)$ is the binary entropy function. As corollaries of our result, we show that (i) for $\delta \gtrsim 0.347$, individual testing is essentially optimal, i.e., $t \geq n(1-o(1))$; and (ii) there is an {adaptivity gap}, since for $\delta \in (0.3471,0.3819)$ known {adaptive} GT algorithms require fewer than $n$ tests to reconstruct ${\cal D}$, whereas our bounds imply that the best nonadaptive algorithm must essentially be individual testing of each element. Perhaps most importantly, our work provides a framework for combining combinatorial and information-theoretic methods for deriving non-trivial lower bounds for a variety of non-linear estimation problems.

1 Introduction

Group testing identifies defective items through pooled tests, but its linear-sparsity regime has received less attention than sublinear sparsity. This work studies non-adaptive testing with reconstruction error and develops tighter converse bounds by exploiting dependence among tests.

1 Introduction

  • For d = δn, prior work had no nontrivial converse beyond the counting bound t ≥ nH(δ), which implies individual testing is optimal only for δ > 0.5.The linear-sparsity regime was comparatively little explored.Source: §1 · pp. 2–3
  • For δ ∈ (0.3471, 0.3819), known zero-error adaptive algorithms use fewer than n tests, while the best nonadaptive algorithms essentially require individual testing.The nonadaptive lower bound holds even when vanishing reconstruction error is allowed.Source: §1 · p. 3
  • The paper focuses on ϵ-error non-adaptive probabilistic group testing in the linear-sparsity regime.The introduction motivates this setting as natural from an information-theoretic perspective.Source: §1 · p. 2, §1.1 · p. 4

1.1 Our Contributions and Techniques

  • The approach tightens the counting converse at its joint-test-entropy step, where the standard independence bound may be loose in this setting.The counting argument lower-bounds test-outcome entropy using input entropy and then upper-bounds it by t.Source: §1.1 · p. 4
  • Theorems 1, 2, and 7 give three new converse bounds; the first two use individual-test entropy and the integer constraint on test size.Theorem 1 observes that individual-test entropies are maximized when each test contains one object; theorem 2 uses that individual-test entropy is below 1 for most δ because test sizes are integer-valued.Source: §1.1 · p. 4
  • Theorem 7 is tighter than the first two bounds because non-adaptive tests share elements, inducing mutual information that tightens the upper bound on joint test entropy.The argument uses Madiman-Tetali inequalities to analyze the resulting correlations among test outcomes.Source: §1.1 · pp. 4–5

2 Impossibility Results for Nonadaptive Group Testing

The section develops lower bounds for probabilistic non-adaptive group testing by tightening bounds on the joint entropy of test outcomes. It proceeds from simple converse bounds to Madiman–Tetali analyses of shared tests, constant-weight matrices, and general matrices.

2.1 Notation and Model

  • Each object is independently defective with probability δ; a fixed binary matrix specifies the tests and their outcomes.Source: §2.1 · p. 5

2.2 Simple Converse Bounds

  • For δ ≥ δ⋆, at least n(1−ϵ/H(δ)) tests are required; Theorem 2’s quantization bound also improves the classical counting bound.Source: §2.2 · pp. 6–7

2.3 Upper Bound via Madiman Tetali inequality

  • The Madiman–Tetali approach uses fractional covers to exploit that jointly observed tests can have entropy below the sum of their individual entropies.Source: §2.3 · p. 7

2.4 Upper bound on H(Y S)

  • For equal-weight tests sharing an object, Theorem 3 upper-bounds their joint entropy.Source: §2.4 · pp. 7–8

2.5 Constant Row Weight Testing Matrix

  • For constant row weight k ≥ 2, column supports form a hypergraph cover used to bound joint test entropy and derive Theorem 5’s asymptotic test lower bound.Source: §2.5 · p. 9

2.6 General Testing Matrix

  • For arbitrary row weights, the matrix is split into submatrices by test weight so the constant-weight analysis can be applied to each.Source: §2.6 · p. 10
  • Theorem 7 gives an asymptotic bound for non-adaptive PGT with independent defect probability δ and error probability at most ϵ; it intersects t/n = 1 at δ ≈ 0.3471.Source: §2.6 · p. 12
  • The results are stated for PGT; most arguments may extend to CGT, but Lemma 4 requires approximation when |S| is nonconstant.Source: §2.6 · p. 12

3 Discussion and Comparison

The comparison reports a non-vanishing improvement over the counting bound and an adaptivity gap. It also notes that integer test sizes make one lower bound piecewise, while larger error tolerance can permit fewer tests.

3 Discussion and Comparison

  • The section compares the theorem 7 bound with an adaptive algorithm's expected test count.The algorithm and its expected number of tests are described, but the supplied passage gives no count value.Source: §3 · p. 12
  • The theorem 7 lower bound exceeds the counting bound by a non-vanishing gap, and the figure also shows an adaptivity gap.The quantization bound improves over the counting bound for a significant region of δ.Source: §3 · p. 12
  • For ϵ > δ, some objects can be ignored during testing, potentially allowing fewer tests.The plotted theorem 7 results use vanishing error, ϵ = o(1).Source: §3 · p. 12
  • Integer constraints on the number of objects per test make the bound in equation (43) discrete and its plot piecewise.The passage attributes this shape to the requirement that each test contain an integer number of objects.Source: §3 · p. 12

4 Future Work / Implications

The discussion identifies unused strength in the entropy bounds and proposes several routes to sharper results. It also points to applying the lower-bound framework to other recovery and testing problems.

4 Future Work / Implications

  • The authors conjecture that every constant δ > 0 requires n − o(n) non-adaptive tests for vanishing error.Their current bound uses the weak Madiman–Tetali form, which ignores gains from conditional entropy.Source: §4 · p. 13
  • The test entropy is minimized at row weight k0(δ), and the reported optimizer varies with δ.As δ decreases, k0(δ) increases while the improvement in the first entropy term reduces.Source: §4 · p. 13
  • For small δ, the conditional Madiman–Tetali form may substantially improve the theorem 7 bound, although its analytical approximations are non-trivial.The discussion links this prospect to increasing average mutual information between test groups as k0(δ) increases.Source: §4 · p. 13
  • Using unions of supports from multiple columns as hyperedges may leave room to improve the theorem 7 bound even with the weak degree form.The proposed change can make many tests share more than one object.Source: §4 · p. 13
  • Combining Delsarte distance-spectrum inequalities with Madiman–Tetali inequalities is proposed as a possible way to tighten the information-theoretic bounds.The authors say it is unclear what such a combination would look like concretely.Source: §4 · p. 13
  • The lower-bound technique may apply to other sparse-recovery problems, threshold group testing, pooled-data problems, and threshold secret-sharing questions.These are presented as prospective applications.Source: §4 · p. 13

A.1 Proof of the remainder of Lemma 4

The supplied proof fragments define events for negative tests, invoke inclusion–exclusion, and then refer back to an earlier step to complete the argument.

A.1 Proof of the remainder of Lemma 4

  • The proof defines E(R) as the event that test Y(R) is negative, with E_l denoting E(R_l).It also defines E as the complement of that event.Source: §A.1 · p. 15
  • The proof invokes inclusion–exclusion in its first step.Source: §A.1 · p. 15
  • The remaining proof repeatedly applies step 1, and the final displayed implication follows from equation (51).The supplied fragment also states that equation (48) follows directly from equation (51).Source: §A.1 · p. 15

3. We have, using step 1 and step 2,

The supplied fragment gives a probability-based justification for equation (52).

3. We have, using step 1 and step 2,

  • Equation (52) follows from a probability relation.Source: §3 · p. 16

A.2 Ungar’s [25] Adaptive Algorithm

This section analyzes the expected test count of Ungar’s adaptive algorithm, which takes objects independently defective with probability δ and returns the defective set. The algorithm partitions items into pairs and performs some tests conditionally.

A.2 Ungar’s [25] Adaptive Algorithm

  • The analysis defines ζ = 1 − δ and considers the algorithm’s expected number of tests.The supplied passage does not state the resulting expected-test expression.Source: §A.2 · pp. 16–17
  • The algorithm also includes a step to test each object individually.Source: §A.2 · p. 16
  • The algorithm partitions n items into n/2 disjoint pairs and processes untested pairs.Its input specifies independent defectivity with probability δ, and its result is the defective set D.Source: §A.2 · p. 16
  • For each pair, the first test is always performed, while the second is performed only if Xi1 ∨ Xi2 = 1.Source: §A.2 · p. 17
  • The third test is performed only if Xi1 = 1.Source: §A.2 · p. 17
Loading 1801.02701v3…