Nonadaptive Group Testing With Random Set of Defectives

DOI10.1109/TIT.2016.2613870MaRDI QIDQ2976472zbMATH OpenFDO

Authors Arya Mazumdar

Publication date 28 April 2017

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

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

Mathematics Subject Classification ID

Combinatorial codes (94B25)

Abstract: In a group testing scheme, a set of tests is designed to identify a small number $t$ of defective items that are present among a large number $N$ of items. Each test takes as input a group of items and produces a binary output indicating whether any defective item is present in the group. In a non-adaptive scheme designing a testing scheme is equivalent to the construction of a disjunct matrix, an $MimesN$ binary matrix where the union of supports of any $t$ columns does not contain the support of any other column. In this paper we consider the scenario where defective items are random and follow simple probability distributions. In particular we consider the cases where 1) each item can be defective independently with probability $fractN$ and 2) each $t$-set of items can be defective with uniform probability. In both cases our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before and it is known that $O(tlogN)$ tests are necessary as well as sufficient (via random coding) in both cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on emph{constant-weight error-correcting codes} and their minimum distance. We go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of the resulting test matrix. With our relaxed requirements, we show that using explicit constant-weight codes (e.g., based on algebraic geometry codes) we may achieve a number of tests equal to $O(tfraclo{g}^{2}Nlogt)$ for both the first and the second cases.

Cited in

(6)

• A recovery algorithm and pooling designs for one-stage noisy group testing under the probabilistic framework
• Non-adaptive hypergeombtric group testing designs for identifying at most two defectives
• An efficient randomized group testing procedure to determine the number of defectives
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Non-iterative sparse signal recovery algorithms for sparse matrices and their guarantees
• Parity-check codes from disjunct matrices

This page was built for publication: Nonadaptive Group Testing With Random Set of Defectives

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