Boolean Compressed Sensing and Noisy Group Testing

Abstract

The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. The single letter characterization is shown to be order-wise tight for many interesting noisy group testing scenarios. Specifically, we consider an additive Bernoulli($q$) noise model where we show that, for $N$ items and $K$ defectives, the number of tests $T$ is $O(\frac{K\log N}{1-q})$ for arbitrarily small average error probability and $O(\frac{K^2\log N}{1-q})$ for a worst case error criterion. We also consider dilution effects whereby a defective item in a positive pool might get diluted with probability $u$ and potentially missed. In this case, it is shown that $T$ is $O(\frac{K\log N}{(1-u{)}^2})$ and $O(\frac{K^2\log N}{(1-u{)}^2})$ for the average and the worst case error criteria, respectively. Furthermore, our bounds allow us to verify existing known bounds for noiseless group testing including the deterministic noise-free case and approximate reconstruction with bounded distortion. Our proof of achievability is based on random coding and the analysis of a Maximum Likelihood Detector, and our information theoretic lower bound is based on Fano's inequality.

In this revision: reorganized the paper, added citations to related work, and fixed some bugs

Cited by in corpus (32)

• Group testing algorithms: bounds and simulations
• The Capacity of Adaptive Group Testing
• The Mutual Information in Random Linear Estimation
• Compressed Genotyping
• Performance of group testing algorithms with near-constant tests-per-item
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Individual testing is optimal for nonadaptive group testing in the linear regime
• Non-adaptive Group Testing: Explicit bounds and novel algorithms
• Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
• Nonadaptive group testing with random set of defectives
• Gaussian Multiple and Random Access in the Finite Blocklength Regime
• Random Access Channel Coding in the Finite Blocklength Regime
• Near-Optimal Noisy Group Testing via Separate Decoding of Items
• The capacity of non-identical adaptive group testing
• The capacity of Bernoulli nonadaptive group testing
• Partition Information and its Transmission over Boolean Multi-Access Channels
• Rates of adaptive group testing in the linear regime
• Almost Separable Matrices
• Improved group testing rates with constant column weight designs
• Asymptotics of Fingerprinting and Group Testing: Tight Bounds from Channel Capacities
• Efficient Probabilistic Group Testing Based on Traitor Tracing
• Adaptive group testing as channel coding with feedback
• Strong converses for group testing in the finite blocklength regime
• Efficient (nonrandom) construction and decoding for non-adaptive group testing
• Non-adaptive pooling strategies for detection of rare faulty items
• Bayesian inference of infected patients in group testing with prevalence estimation
• On the All-Or-Nothing Behavior of Bernoulli Group Testing
• Asymptotics of Fingerprinting and Group Testing: Capacity-Achieving Log-Likelihood Decoders
• Asymptotic Error Free Partitioning over Noisy Boolean Multiaccess Channels
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Phase transition in binary compressed sensing based on $L_1$-norm minimization
• Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing