Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
arXiv:1010.2441 · doi:10.1109/ALLERTON.2010.5707018
Abstract
An information theoretic perspective on group testing problems has recently been proposed by Atia and Saligrama, in order to characterise the optimal number of tests. Their results hold in the noiseless case, where only false positives occur, and where only false negatives occur. We extend their results to a model containing both false positives and false negatives, developing simple information theoretic bounds on the number of tests required. Based on these bounds, we obtain an improved order of convergence in the case of false negatives only. Since these results are based on (computationally infeasible) joint typicality decoding, we propose a belief propagation algorithm for the detection of defective items and compare its actual performance to the theoretical bounds.
5 pages, 3 figures, presented at the Forty-Eighth Annual Allerton Conference on Communication, Control, and Computing, September 29 - October 1, 2010, Monticello, IL, USA
References in corpus (3)
Cited by in corpus (25)
- Active sequential hypothesis testing
- Group testing algorithms: bounds and simulations
- Non-adaptive Group Testing: Explicit bounds and novel algorithms
- Near-Optimal Noisy Group Testing via Separate Decoding of Items
- The capacity of non-identical adaptive group testing
- Almost Separable Matrices
- Noisy Adaptive Group Testing using Bayesian Sequential Experimental Design
- Asymptotics of Fingerprinting and Group Testing: Tight Bounds from Channel Capacities
- Efficient Probabilistic Group Testing Based on Traitor Tracing
- Adaptive group testing as channel coding with feedback
- Improved bounds for noisy group testing with constant tests per item
- Semi-Quantitative Group Testing: A Unifying Framework for Group Testing with Applications in Genotyping
- On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing
- Interference Mitigation in Large Random Wireless Networks
- Bayesian inference of infected patients in group testing with prevalence estimation
- Boolean Matrix Factorization and Noisy Completion via Message Passing
- Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms
- Noisy group testing via spatial coupling
- Asymptotics of Fingerprinting and Group Testing: Capacity-Achieving Log-Likelihood Decoders
- Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
- On Finding a Subset of Healthy Individuals from a Large Population
- Online neural connectivity estimation with ensemble stimulation
- Bitwise MAP Algorithm for Group Testing based on Holographic Transformation
- Decision Theoretic Cutoff and ROC Analysis for Bayesian Optimal Group Testing
- Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing