Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms

DOI10.1109/TIT.2014.2310477MaRDI QIDQ2986417zbMATH OpenFDO

Authors Chun Lam Chan, Sidharth Jaggi, Venkatesh Saligrama, Samar Agnihotri

Publication date 16 May 2017

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

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

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Paired and multiple comparisons; multiple testing (62J15) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Source coding (94A29)

Abstract: We consider some computationally efficient and provably correct algorithms with near-optimal sample-complexity for the problem of noisy non-adaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be "sparse". We consider non-adaptive randomly pooling measurements, where pools are selected randomly and independently of the test outcomes. We also consider a model where noisy measurements allow for both some false negative and some false positive test outcomes (and also allow for asymmetric noise, and activation noise). We consider three classes of algorithms for the group testing problem (we call them specifically the "Coupon Collector Algorithm", the "Column Matching Algorithms", and the "LP Decoding Algorithms" -- the last two classes of algorithms (versions of some of which had been considered before in the literature) were inspired by corresponding algorithms in the Compressive Sensing literature. The second and third of these algorithms have several flavours, dealing separately with the noiseless and noisy measurement scenarios. Our contribution is novel analysis to derive explicit sample-complexity bounds -- with all constants expressly computed -- for these algorithms as a function of the desired error probability; the noise parameters; the number of items; and the size of the defective set (or an upper bound on it). We also compare the bounds to information-theoretic lower bounds for sample complexity based on Fano's inequality and show that the upper and lower bounds are equal up to an explicitly computable universal constant factor (independent of problem parameters).

Cited in

(17)

• Nonadaptive algorithms for threshold group testing
• Random and quasi-random designs in group testing
• Sampling schemes and recovery algorithms for functions of few coordinate variables
• Noise-Resilient Group Testing: Limitations and Constructions
• Optimizing Nonadaptive Group Tests for Objects with Heterogeneous Priors
• A chasm between identity and equivalence testing with conditional queries
• Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Almost separable matrices
• Explicit Nonadaptive Combinatorial Group Testing Schemes
• Nonadaptive Group Testing Based on Sparse Pooling Graphs
• scientific article; zbMATH DE number 7758315 (Why is no real title available?)
• Non-adaptive Group-Testing Aggregate MAC Scheme
• Non-iterative sparse signal recovery algorithms for sparse matrices and their guarantees
• Dynamic batching of online arrivals to leverage economies of scale
• Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing
• Nonadaptive group testing with lies: probabilistic existence theorems

This page was built for publication: Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms

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