## 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 semiadaptive 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.

Original language | English (US) |
---|---|

Article number | 7124525 |

Pages (from-to) | 4396-4410 |

Number of pages | 15 |

Journal | IEEE Transactions on Signal Processing |

Volume | 63 |

Issue number | 16 |

DOIs | |

State | Published - Aug 15 2015 |

## Keywords

- Adaptive group testing
- Boolean compressed sensing
- Huffman coding
- binomial group testing
- dynamical group testing
- information-theoretic bounds
- nonadaptive design
- semiadaptive algorithms

## ASJC Scopus subject areas

- Signal Processing
- Electrical and Electronic Engineering