Computer Science – Information Theory
Scientific paper
2009-09-18
Computer Science
Information Theory
In Proceedings of the Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing
Scientific paper
Detection of defective members of large populations has been widely studied in the statistics community under the name "group testing", a problem which dates back to World War II when it was suggested for syphilis screening. There the main interest is to identify a small number of infected people among a large population using collective samples. In viral epidemics, one way to acquire collective samples is by sending agents inside the population. While in classical group testing, it is assumed that the sampling procedure is fully known to the reconstruction algorithm, in this work we assume that the decoder possesses only partial knowledge about the sampling process. This assumption is justified by observing the fact that in a viral sickness, there is a chance that an agent remains healthy despite having contact with an infected person. Therefore, the reconstruction method has to cope with two different types of uncertainty; namely, identification of the infected population and the partially unknown sampling procedure. In this work, by using a natural probabilistic model for "viral infections", we design non-adaptive sampling procedures that allow successful identification of the infected population with overwhelming probability 1-o(1). We propose both probabilistic and explicit design procedures that require a "small" number of agents to single out the infected individuals. More precisely, for a contamination probability p, the number of agents required by the probabilistic and explicit designs for identification of up to k infected members is bounded by m = O(k^2 (log n)/p^2) and m = O(k^2 (log n)^2 /p^2), respectively. In both cases, a simple decoder is able to successfully identify the infected population in time O(mn).
Cheraghchi Mahdi
Hormati Ali
Karbasi Amin
Vetterli Martin
No associations
LandOfFree
Compressed Sensing with Probabilistic Measurements: A Group Testing Solution 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 Compressed Sensing with Probabilistic Measurements: A Group Testing Solution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed Sensing with Probabilistic Measurements: A Group Testing Solution will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-277527