Compressed sensing with probabilistic measurements: A group testing solution

Compressed sensing with probabilistic measurements: A group testing solution. Cheraghchi, M., Hormati, A., Karbasi, A., & Vetterli, M. In Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, pages 30–35, 2009. Extended version in IEEE Transactions on Information Theory.

Link

Paper doi abstract bibtex

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

@INPROCEEDINGS{ref:conf:CHKV09,
  author =	 {Mahdi Cheraghchi and Ali Hormati and Amin Karbasi
                  and Martin Vetterli},
  title =	 {Compressed sensing with probabilistic measurements:
                  A group testing solution},
  booktitle =	 {Proceedings of the 47th {Annual Allerton Conference
                  on Communication, Control, and Computing}},
  year =	 2009,
  pages =	 {30--35},
  note =	 {Extended version in {IEEE Transactions on
                  Information Theory}.},
  doi =		 {10.1109/ALLERTON.2009.5394829},
  url_Link =	 {https://ieeexplore.ieee.org/document/5394829},
  url_Paper =	 {https://arxiv.org/abs/0909.3508},
  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 \textit{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
                  \textit{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)$.  }
}

Downloads: 0