Model-Based and Graph-Based Priors for Group Testing

Abstract

The goal of the group testing problem is to identify a set of defective items within a larger set of items, using suitably-designed tests whose outcomes indicate whether any defective item is present. In this paper, we study how the number of tests can be significantly decreased by leveraging the structural dependencies between the items, i.e., by incorporating prior information. To do so, we pursue two different perspectives: (i) As a generalization of the uniform combinatorial prior, we consider the case that the defective set is uniform over a \emph{subset} of all possible sets of a given size, and study how this impacts the information-theoretic limits on the number of tests for approximate recovery; (ii) As a generalization of the i.i.d.~prior, we introduce a new class of priors based on the Ising model, where the associated graph represents interactions between items. We show that this naturally leads to an Integer Quadratic Program decoder, which can be converted to an Integer Linear Program and/or relaxed to a non-integer variant for improved computational complexity, while maintaining strong empirical recovery performance.

arXiv commentIEEE Transactions on Signal Processing

References in corpus (8)

• Model-Based Compressive Sensing
• Group testing algorithms: bounds and simulations
• Performance of group testing algorithms with near-constant tests-per-item
• Group Testing with Prior Statistics
• Noise-Resilient Group Testing: Limitations and Constructions
• The capacity of non-identical adaptive group testing
• Contact Tracing Enhances the Efficiency of COVID-19 Group Testing
• Group Testing with a Graph Infection Spread Model

Cited by in corpus (1)

• Group Testing with Side Information via Generalized Approximate Message Passing