Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach

DOI10.1109/TIT.2020.2970184zbMATH Open1448.62036arXiv1808.09143OpenAlexW3004406280MaRDI QIDQ5124399FDOQ5124399

Oliver Johnson, Jonathan Scarlett

Publication date: 29 September 2020

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

Abstract: The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. We study the noisy version of this problem, where the outcome of each standard noiseless group test is subject to independent noise, corresponding to passing the noiseless result through a binary channel. We introduce a class of algorithms that we refer to as Near-Definite Defectives (NDD), and study bounds on the required number of tests for asymptotically vanishing error probability under Bernoulli random test designs. In addition, we study algorithm-independent converse results, giving lower bounds on the required number of tests under Bernoulli test designs. Under reverse Z-channel noise, the achievable rates and converse results match in a broad range of sparsity regimes, and under Z-channel noise, the two match in a narrower range of dense/low-noise regimes. We observe that although these two channels have the same Shannon capacity when viewed as a communication channel, they can behave quite differently when it comes to group testing. Finally, we extend our analysis of these noise models to a general binary noise model (including symmetric noise), and show improvements over known existing bounds in broad scaling regimes.

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

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (3)

• Generalized framework for group testing: queries, feedbacks and adversaries
• Noise-Resilient Group Testing: Limitations and Constructions
• A recovery algorithm and pooling designs for one-stage noisy group testing under the probabilistic framework

   Recommendations

• Nonadaptive Group Testing With Random Set of Defectives 👍 👎
• Noisy Adaptive Group Testing: Bounds and Algorithms 👍 👎
• Bounds for nonadaptive group tests to estimate the amount of defectives 👍 👎
• Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives 👍 👎
• Noisy Adaptive Group Testing via Noisy Binary Search 👍 👎
• Title not available (Why is that?) 👍 👎
• Non-adaptive group testing in the presence of errors 👍 👎
• Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms 👍 👎
• Optimal deterministic group testing algorithms to estimate the number of defectives 👍 👎
• Optimal deterministic group testing algorithms to estimate the number of defectives 👍 👎

This page was built for publication: Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach

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