Noisy group testing via spatial coupling

Abstract

We study the problem of identifying a small set $k\sim n^{\theta }$, $0<\theta <1$, of infected individuals within a large population of size $n$ by testing groups of individuals simultaneously. All tests are conducted concurrently. The goal is to minimise the total number of tests required. In this paper we make the (realistic) assumption that tests are noisy, i.e.\ that a group that contains an infected individual may return a negative test result or one that does not contain an infected individual may return a positive test results with a certain probability. The noise need not be symmetric. We develop an algorithm called SPARC that correctly identifies the set of infected individuals up to $o(k)$ errors with high probability with the asymptotically minimum number of tests. Additionally, we develop an algorithm called SPEX that exactly identifies the set of infected individuals w.h.p. with a number of tests that matches the information-theoretic lower bound for the constant column design, a powerful and well-studied test design.

References in corpus (16)

• Statistical physics of inference: Thresholds and algorithms
• Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
• Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
• The Capacity of Adaptive Group Testing
• Information-theoretic thresholds from the cavity method
• Evolution of scaling emergence in large-scale spatial epidemic spreading
• Performance of group testing algorithms with near-constant tests-per-item
• Information-theoretic and algorithmic thresholds for group testing
• Optimal group testing
• The capacity of Bernoulli nonadaptive group testing
• Rates of adaptive group testing in the linear regime
• Decoding from Pooled Data: Phase Transitions of Message Passing
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Non-adaptive pooling strategies for detection of rare faulty items
• Improved bounds for noisy group testing with constant tests per item
• Exact Thresholds for Noisy Non-Adaptive Group Testing