Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Compressed Sensing with Probabilistic Measurements: A Group Testing Solution
 
conference paper

Compressed Sensing with Probabilistic Measurements: A Group Testing Solution

Cheraghchi, Mahdi
•
Hormati, Ali  
•
Karbasi, Amin  
Show more
2009
47th Annual Allerton Conference on Communication, Control, and Computing
47th Annual Allerton Conference on Communication, Control, and Computing

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 \emph{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 \emph{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^2 n) / p^2)$, respectively. In both cases, a simple decoder is able to successfully identify the infected population in time $O(mn)$.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1109/ALLERTON.2009.5394829
Web of Science ID

WOS:000279627100005

Author(s)
Cheraghchi, Mahdi
Hormati, Ali  
Karbasi, Amin  
Vetterli, Martin  
Date Issued

2009

Published in
47th Annual Allerton Conference on Communication, Control, and Computing
Start page

30

End page

35

Subjects

algoweb_misc

URL

URL

http://www.csl.illinois.edu/allerton/
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTHC  
LCAV  
Event nameEvent placeEvent date
47th Annual Allerton Conference on Communication, Control, and Computing

University of Illinois at Urbana-Champaign

September 30 – October 2

Available on Infoscience
September 18, 2009
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/42748
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés