Boolean Compressed Sensing and Noisy Group Testing

DOI10.1109/TIT.2011.2178156MaRDI QIDQ5272078zbMATH OpenOpenAlexDBLPWikidataFDO

Authors George K. Atia, Venkatesh Saligrama

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial probability (60C05) Sampling theory in information and communication theory (94A20)

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(fracKlogN1-q)$ for arbitrarily small average error probability and $O(frac{K}^{2}logN1-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(fracKlogN(1-u{)}^2)$ and $O(frac{K}^{2}logN(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.

Cited in

(12)

• The landscape of empirical risk for nonconvex losses
• A recovery algorithm and pooling designs for one-stage noisy group testing under the probabilistic framework
• Real-valued group testing for quantitative molecular assays
• Performance Bounds for Grouped Incoherent Measurements in Compressive Sensing
• Search for sparse active inputs: a review
• A new strongly competitive group testing algorithm with small sequentiality
• Almost separable matrices
• scientific article; zbMATH DE number 7758315 (Why is no real title available?)
• An interpretable classification method for predicting drug resistance in M. tuberculosis
• Optimal Dorfman group testing for symmetric distributions
• Twenty questions with random error
• A tight lower bound on non-adaptive group testing estimation

This page was built for publication: Boolean Compressed Sensing and Noisy Group Testing

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