Pooled testing with compressive sensing

Jing Yang, Ashley Prater-Bennette

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this work, we consider compressed sensing based pooled testing, where k out of n items are defective (with a non-zero state). Each time, a subset of items are mixed together, and a real-valued quantitative measurement is obtained, where the measurement equals a random linear combination of the states of the mixed items. Our objective is to detect the k defective items based on the quantitative measurements. This problem arises in a variety of applications, including viral infection diagnosis, network state inference, etc. We assume that each item can be mixed in a limited number of tests, and the mixing coefficients are drawn independently according to a standard Gaussian distribution. We obtain sufficient conditions on the number of tests required for the exact detection of the defective items using an exhaustive search decoder. Our result indicates that the sample complexity scales in the order of O(k? log(nk)), where ? is approximately the minimum of the n proportions of tests that include individual items. Our result recovers the optimal sample complexity in compressive sensing when ? = 1. The performance of the exhaustive search decoder is evaluated numerically under various assumptions on the mixing constraints, signal to noise ratio, and sparsity level.

Original languageEnglish (US)
Title of host publicationBig Data III
Subtitle of host publicationLearning, Analytics, and Applications
EditorsFauzia Ahmad, Panos P. Markopoulos, Bing Ouyang
ISBN (Electronic)9781510642973
StatePublished - 2021
EventBig Data III: Learning, Analytics, and Applications 2021 - Virtual, Online, United States
Duration: Apr 12 2021Apr 16 2021

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
ISSN (Print)0277-786X
ISSN (Electronic)1996-756X


ConferenceBig Data III: Learning, Analytics, and Applications 2021
Country/TerritoryUnited States
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Pooled testing with compressive sensing'. Together they form a unique fingerprint.

Cite this