Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing

DOI10.1109/TSP.2015.2446433zbMATH Open1394.94170arXiv1410.5373MaRDI QIDQ4580755FDOQ4580755

Authors:

Publication date: 22 August 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: We introduce a novel probabilistic group testing framework, termed Poisson group testing, in which the number of defectives follows a right-truncated Poisson distribution. The Poisson model has a number of new applications, including dynamic testing with diminishing relative rates of defectives. We consider both nonadaptive and semi-adaptive identification methods. For nonadaptive methods, we derive a lower bound on the number of tests required to identify the defectives with a probability of error that asymptotically converges to zero; in addition, we propose test matrix constructions for which the number of tests closely matches the lower bound. For semi-adaptive methods, we describe a lower bound on the expected number of tests required to identify the defectives with zero error probability. In addition, we propose a stage-wise reconstruction algorithm for which the expected number of tests is only a constant factor away from the lower bound. The methods rely only on an estimate of the average number of defectives, rather than on the individual probabilities of subjects being defective.

Full work available at URL: https://arxiv.org/abs/1410.5373

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Cited In (1)

• A recovery algorithm and pooling designs for one-stage noisy group testing under the probabilistic framework

This page was built for publication: Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580755)