Compressed Sensing with Probabilistic Measurements: A Group Testing Solution
File(s)
Accepted version
Author(s)
Cheraghchi, Mahdi
Hormati, Ali
Karbasi, Amin
Vetterli, Martin
Type
Conference Paper
Abstract
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(k2(log n)/p2) and m = O(k2 (log2 n)/p2), respectively. In both cases, a simple decoder is able to successfully identify the infected population in time O(mn).
Date Issued
2010-01-22
Date Acceptance
2009-09-30
Citation
2009 47TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING, VOLS 1 AND 2, 2010, pp.30-35
ISBN
978-1-4244-5870-7
ISSN
2474-0195
Publisher
IEEE
Start Page
30
End Page
35
Journal / Book Title
2009 47TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING, VOLS 1 AND 2
Copyright Statement
© 2009 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000279627100005&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Source
47th Annual Allerton Conference on Communication, Control, and Computing
Subjects
Science & Technology
Technology
Computer Science, Theory & Methods
Engineering, Electrical & Electronic
Telecommunications
Computer Science
Engineering
COVER-FREE FAMILIES
Publication Status
Published
Start Date
2009-09-30
Finish Date
2009-10-02
Coverage Spatial
Monticello, IL
Date Publish Online
2010-01-22