Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction

Details Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction

2010-10-12

arxiv.org/abs/1010.2441v1

Computer Science

Information Theory

5 pages, 3 figures, presented at the Forty-Eighth Annual Allerton Conference on Communication, Control, and Computing, Septemb

Scientific paper

10.1109/ALLERTON.2010.5707018

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.

Affiliated with

Also associated with

No associations

Rating

Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-608861