2010 · 98 citations · 8 references
Natural SciencesComputer ScienceMathematicsAlgorithmsInformation TheoryProbability TheoryBayesian InferenceHypothesis TestingStatistical InferenceBelief PropagationBelief Propagation Decoding
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.
8
The Detection of Defective Members of Large Populations
Robert Dorfman · The Annals of Mathematical Statistics · 1943 · 1.7K citations · Full text
Life Sciences, Biology, Genetics +4
1 Boolean Compressed Sensing and Noisy Group Testing
George Atia, Venkatesh Saligrama · 2013 · 228 citations
Yaniv Erlich, Assaf Gordon, Michael Brand et al. · IEEE Transactions on Information Theory · 2010 · 58 citations · Full text
Statistical Physics of Group Testing
2007 · 32 citations