Compressed Sensing with Probabilistic Measurements: A Group Testing Solution

Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, Martin VetterliarXiv 2009 · OpenReview

TL;DR

This paper tackles the challenge of identifying infected individuals in a large population using group testing, but with a twist: the sampling process itself is uncertain. They introduce a probabilistic model for how agents might get infected and propose novel non-adaptive sampling strategies that can accurately identify infected individuals with a high probability, using a significantly reduced number of agents compared to traditional methods.

What Problem Does This Paper Address?

Imagine a scenario like a flu epidemic where you need to identify who is infected in a large population. Testing everyone individually is prohibitively expensive. Group testing offers a solution by pooling samples, but this typically assumes we know exactly which samples are in each pool. This paper addresses a more realistic scenario: what if the "samplers" (agents) themselves are not perfect? In a viral outbreak, an agent might interact with an infected person but not get infected themselves, or the exact contacts an agent makes might not be perfectly recorded. This introduces two layers of uncertainty: identifying the infected individuals and dealing with the unreliable sampling process. The authors aim to design efficient sampling strategies and recovery algorithms that can overcome both these challenges.

Methods

The core of the paper lies in developing new sampling strategies and a corresponding decoding mechanism. They model the uncertainty in the sampling process using a "contamination probability" ($p$), representing the chance an agent doesn't get infected despite contact with an infected individual.

  • Probabilistic Model: They introduce a probabilistic model where each contact between an agent and an infected person results in the agent getting infected with probability $p$. This leads to a "stochastic sampling matrix" that is not perfectly known to the decoder.
  • Adversarial Setting: To simplify analysis and leverage existing tools, they first consider an "adversarial setting." Here, instead of random uncertainty, an adversary can arbitrarily flip a limited number of entries in the sampling matrix to zero. This is a stronger condition that, if solved, helps solve the stochastic problem.
  • Disjunct Matrices: The adversarial problem is framed in terms of "disjunct matrices," a concept from combinatorial group testing. They define and utilize properties of $(k, e)$-disjunct matrices, which are crucial for distinguishing between different sparse sets of infected individuals even with some errors.
  • Probabilistic Construction: They propose a method to construct the "contact matrix" (which defines which agents could interact with whom) probabilistically. Each entry is set to 1 with a certain probability, and they show that with a sufficiently large number of agents ($m$), this matrix is likely to be $(k, e)$-disjunct.
  • Explicit Construction: For guaranteed performance, they also offer a deterministic construction based on Reed-Solomon codes. This method provides a concrete way to build the contact matrix.
  • Distance Decoder: A simple decoding algorithm is proposed. It leverages the $(k, e)$-disjunct property by checking if the number of "missing" contacts in an agent's log (compared to the potential contacts with infected individuals) is within the error bound $e$.

Datasets

Not discussed in the paper. The problem is theoretical and focuses on designing sampling strategies rather than evaluating them on specific real-world datasets.

Key Insights and Ideas

  • Uncertainty is Realistic: The paper highlights that real-world sampling processes are rarely perfect. Modeling this uncertainty (e.g., through contamination probability) is crucial for practical applications like epidemic tracking.
  • Adversarial Solves Stochastic: The clever framing of the problem in an adversarial setting first, and then showing how a solution to that problem translates to the stochastic setting, is a powerful technique. It allows them to use combinatorial tools effectively.
  • Disjunct Matrices as a Key Tool: The concept of $(k, e)$-disjunct matrices is central to guaranteeing unique identification of infected individuals, even when the sampling process is noisy.
  • Efficiency Gains: Both probabilistic and explicit constructions achieve significant reductions in the number of agents required, making large-scale testing more feasible. The bounds are expressed in terms of the number of infected individuals ($k$), population size ($n$), and the contamination probability ($p$).

Key Results

  • Probabilistic Construction: Achieves $m = O(k^2 (\log n)/p^2)$ agents and an error probability of $1-o(1)$. This means the number of agents grows quadratically with the number of infected individuals and inversely with the square of the contamination probability.
  • Explicit Construction: Requires slightly more agents, $m = O(k^2 (\log^2 n)/p^2)$, but offers a deterministic guarantee for correct reconstruction. This is a factor of $O(\log n)$ worse than the probabilistic approach but provides certainty.
  • Simple Decoder: The proposed "distance decoder" is computationally efficient, with a time complexity of $O(mn)$.

Limitations and Future Work

  • Sparsity Assumption: The methods rely on the assumption that the number of infected individuals ($k$) is significantly smaller than the total population ($n$). If $k$ approaches $n$, traditional individual testing becomes more efficient.
  • Parameter Estimation: The paper assumes $k$ and $p$ are known. In practice, estimating these parameters might be a challenge.
  • Non-Adaptive Sampling: The focus is on non-adaptive sampling (where the entire sampling plan is fixed beforehand). Adaptive strategies, where sampling decisions can be made based on intermediate results, might offer further efficiency gains.
  • Generalization: Exploring extensions to more complex infection models or different types of measurement errors could be valuable future work.

Summary updated

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(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).
BibTeX
@misc{cheraghchi2009compressed,
  author = {Mahdi Cheraghchi and Ali Hormati and Amin Karbasi and Martin Vetterli},
  title = {{Compressed Sensing with Probabilistic Measurements: A Group Testing Solution}},
  year = {2009},
  eprint = {0909.3508},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0909.3508},
}
Figure