The capacity of non-identical adaptive group testing

Abstract

We consider the group testing problem, in the case where the items are defective independently but with non-constant probability. We introduce and analyse an algorithm to solve this problem by grouping items together appropriately. We give conditions under which the algorithm performs essentially optimally in the sense of information-theoretic capacity. We use concentration of measure results to bound the probability that this algorithm requires many more tests than the expected number. This has applications to the allocation of spectrum to cognitive radios, in the case where a database gives prior information that a particular band will be occupied.

arXiv commentTo be presented at Allerton 2014

References in corpus (6)

• Boolean Compressed Sensing and Noisy Group Testing
• Group testing algorithms: bounds and simulations
• Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
• The Capacity of Adaptive Group Testing
• Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
• Group Testing with Prior Statistics

Cited by in corpus (5)

• Individual testing is optimal for nonadaptive group testing in the linear regime
• Rates of adaptive group testing in the linear regime
• Strong converses for group testing in the finite blocklength regime
• Model-Based and Graph-Based Priors for Group Testing
• Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing