PaperlayerView exact revision on arXiv

Source-linked AI summary

The Capacity of Adaptive Group Testing

Leonardo Baldassini, Oliver Johnson, Matthew Aldridge

arXiv:1301.7023v2cs.ITmath.IT

TL;DR

The paper asks how to characterize capacity in adaptive group testing and noisy variants. It introduces a capacity framework and relates noisy group testing to equivalent communication channels. It establishes capacity 1 for noiseless testing and 1 − p for the erasure model when K = o(N).

  • Problem

    The paper studies how many tests are needed to identify a known number of defectives and how to characterize capacity for adaptive and noisy group testing.

    Source: §I · pp. 1–2

  • Method

    It defines group-testing capacity, bounds noisy-model capacities using equivalent communication channels, and combines a new information-theoretic lower bound with existing performance guarantees.

    Source: §I · p. 2

  • Results

    For K = o(N), noiseless adaptive group testing has capacity C = 1 and the erasure model has capacity C = 1 − p.

    Source: §I · p. 2

  • Takeaways & Limitations

    Equivalent-channel capacities provide upper bounds for noisy group testing, but do not establish exact capacity for every noise model.

    Source: §I · p. 2

    Exact capacity values for other cases, including non-adaptive problems, remain to be found.

    Source: §V · p. 5

Abstract

from arXiv · show

We define capacity for group testing problems and deduce bounds for the capacity of a variety of noisy models, based on the capacity of equivalent noisy communication channels. For noiseless adaptive group testing we prove an information-theoretic lower bound which tightens a bound of Chan et al. This can be combined with a performance analysis of a version of Hwang's adaptive group testing algorithm, in order to deduce the capacity of noiseless and erasure group testing models.

I. INTRODUCTION AND NOTATION

The paper studies adaptive group testing through a capacity framework, proving capacity 1 for noiseless testing when defectives are sparse and deriving bounds for noisy models. Its noisy-model principle compares group-testing capacity with that of an equivalent communication channel.

I. INTRODUCTION AND NOTATION

  • The goal is to identify defective items with few tests; K is assumed known, and adaptive test choices depend on earlier outcomes.The paper distinguishes noiseless tests from additive, symmetric-error, and erasure noise models.Source: §I · p. 1
  • The paper focuses on sparse defectives, K = o(N), and uses K = N^(1−β), 0 < β < 1, as a benchmark parameterization.Group testing is especially advantageous when the defective set is sparse.Source: §I · pp. 1–2
  • The adaptive noiseless group-testing capacity is C = 1 whenever K = o(N).The proof combines a new information-theoretic lower bound with existing performance guarantees.Source: §I · p. 2
  • Theorem 1.2 combines a new information-theoretic lower bound with existing performance guarantees to establish the noiseless capacity result.The lower bound is Theorem 3.1.Source: §I · p. 2
  • A noisy group-testing capacity cannot exceed that of the equivalent communication channel, since test outcomes encode the defective set under restricted tests.A test can only determine whether its tested subset intersects the defective set.Source: §I · p. 2
  • For K = o(N), erasure-model capacity is C = 1 − p; symmetric-error and additive models receive channel-based upper bounds, with equality conjectured.The symmetric-error bound is C ≤ 1 − h(p); the additive-model bound is the capacity of a Z-channel.Source: §I · p. 2

II. EXISTING PERFORMANCE GUARANTEES

The section reviews adaptive testing guarantees and compares Hwang’s Generalized Binary Splitting Algorithm with repeated binary testing and the non-adaptive COMP algorithm. It highlights asymptotic gains from adaptivity, especially when the defective fraction is relatively high.

II. EXISTING PERFORMANCE GUARANTEES

  • Repeated Binary Testing is guaranteed to succeed using K⌈log2 N⌉ ≤ K log2 N + K tests.Its repeated searches begin with large sets likely to contain defectives, making early tests uninformative.Source: §II · p. 2
  • Hwang’s Generalized Binary Splitting Algorithm tests groups sized to make positive outcomes likely near 1/2, then uses binary search to locate a defective.Hwang’s bound is described as close to optimal.Source: §II · pp. 2–3
  • COMP recovers the defective set with error probability ≤N^−δ using T = ((1 + δ)e)K ln N tests.Source: §II · p. 3
  • Adaptivity offers asymptotic gains over COMP’s non-adaptive bound, greatest when β is small and defectives are relatively numerous.The comparison considers K(N) = N^(1−β).Source: §II · p. 3

III. NEW INFORMATION-THEORETIC LOWER BOUND

Theorem 3.1 gives an information-theoretic success-probability bound for adaptive and non-adaptive group testing. The paper presents it as stronger than the prior bound in and identifies exponential decay below the test threshold as new.

III. NEW INFORMATION-THEORETIC LOWER BOUND

  • Theorem 3.1 bounds recovery success probability for T tests and applies to both adaptive and non-adaptive group testing.The theorem is the paper's new information-theoretic lower bound.Source: §III · p. 3
  • For each outcome vector y, the inverse-image set A_y contains candidate defective sets, and optimal decoding succeeds with probability 1/|A_y|.The testing procedure maps each putative defective set to its test-outcome vector.Source: §III · p. 3
  • Below the test count needed for certain recovery, success probability decays exponentially; the paper calls this new and a strengthening of.The paper contrasts this with the 'magic number' lower bound for certain recovery, which it describes as folklore.Source: §III · p. 3
  • The bound yields a strong converse: under the stated sub-threshold condition, P(suc) tends to zero.The paper distinguishes this from, which proves only a weak converse, and says the bound in (5) is significantly stronger than (6).Source: §III · pp. 3–4

IV. A TIGHTER UPPER BOUND

A refined version of Hwang’s algorithm controls sample sizes so negative tests are just less likely than positive tests, tightening the gap to the lower bound. The analysis gives a test-count bound and explains why the number of negative tests does not affect its final form.

IV. A TIGHTER UPPER BOUND

  • The algorithm controls binary-searched sample sizes to keep the probability of a negative test just below 1/2, reducing the gap to the lower bound from K to under K/2.The analysis uses truncation of binomial coefficients and bounds the conditional probability of a negative sample after consecutive negative tests.Source: §IV · p. 4
  • The analysis groups tests into K rounds of negative tests followed by a positive test, then uses binary search to locate a defective.The round structure tracks the size of each subproblem.Source: §IV · p. 4
  • Possible Defectives are items not yet seen in a negative test, and the analysis tracks their counts by round and after consecutive negative tests.It also tracks the number of defectives remaining in each round and the last negative-test time.Source: §IV · p. 4
  • Ttot ≤ K log N + (1 + log ln 2)K − log K! + R bounds the tests for the refined algorithm, where R is negative.The bound is stated in Theorem 4.3.Source: §IV · p. 5
  • The negative random terms are difficult to characterize further, but the number of negative tests cancels out of the final bound.The cancellation follows because summing the round expressions creates a double sum whose coefficients of Ti cancel.Source: §IV · p. 5

V. CONCLUSION

The paper establishes capacity 1 for noiseless adaptive group testing and 1 − p for the erasure model, while leaving exact capacities for other noise models and non-adaptive problems open.

V. CONCLUSION

  • A sharper information-theoretic lower bound establishes capacity 1 for noiseless adaptive group testing and 1 − p for erasure group testing; exact capacities for other noise models and non-adaptive problems remain open.Source: §V · p. 5
Loading 1301.7023v2…