Theoretical Bounds on Performance in Threshold Group Testing Schemes
Open Access
- 21 April 2020
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 8 (4) , 637
Abstract
A threshold group testing (TGT) scheme with lower and upper thresholds is a general model of group testing (GT) which identifies a small set of defective samples. In this paper, we consider the TGT scheme that require the minimum number of tests. We aim to find lower and upper bounds for finding a set of defective samples in a large population. The decoding for the TGT scheme is exploited by minimization of the Hamming weight in channel coding theory and the probability of error is also defined. Then, we derive a new upper bound on the probability of error and extend a lower bound from conventional one to the TGT scheme. We show that the upper and lower bounds well match with each other at the optimal density ratio of the group matrix. In addition, we conclude that when the gaps between the two thresholds in the TGT framework increase, the group matrix with a high density should be used to achieve optimal performance.Keywords
Funding Information
- National Research Foundation of Korea (NRF-2017R1C1B5075823)
This publication has 28 references indexed in Scilit:
- An Almost Optimal Algorithm for Generalized Threshold Group Testing with InhibitorsJournal of Computational Biology, 2011
- Covering and radius-covering arrays: Constructions and classificationDiscrete Applied Mathematics, 2010
- Bounds and constructions for key distribution schemesAdvances in Mathematics of Communications, 2009
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006
- Digital fingerprinting codes: problem statements, constructions, identification of traitorsIEEE Transactions on Information Theory, 2003
- Superimposed codes for the multiaccess binary adder channelIEEE Transactions on Information Theory, 1995
- Forward collision resolution-a technique for random multiple-access to the adder channelIEEE Transactions on Information Theory, 1993
- Born again group testing: Multiaccess communicationsIEEE Transactions on Information Theory, 1985
- The Detection of Defective Members of Large PopulationsThe Annals of Mathematical Statistics, 1943