Back to Search
Start Over
Computationally Tractable Algorithms for Finding a Subset of Non-Defective Items From a Large Population.
- Source :
- IEEE Transactions on Information Theory; Nov2017, Vol. 63 Issue 11, p7149-7165, 17p
- Publication Year :
- 2017
-
Abstract
- In the classical non-adaptive group testing setup, pools of items are tested together, and the main goal of a recovery algorithm is to identify the complete defective set given the outcomes of different group tests. In contrast, the main goal of a non-defective subset recovery algorithm is to identify a subset of non-defective items given the test outcomes. In this paper, we present a suite of computationally efficient and analytically tractable non-defective subset recovery algorithms. By analyzing the probability of error of the algorithms, we obtain bounds on the number of tests required for non-defective subset recovery with arbitrarily small probability of error. Our analysis accounts for the impact of both the additive noise (false positives) and dilution noise (false negatives). By comparing with information theoretic lower bounds, we show that the upper bounds on the number of tests are orderwise tight up to a \log ^2K factor, where $K$ is the number of defective items. We also provide simulation results that compare the relative performance of the different algorithms and reveal insights into their practical utility. The proposed algorithms significantly outperform the straightforward approaches of testing items one-by-one, and of first identifying the defective set and then choosing the non-defective items from the complement set, in terms of the number of measurements required to ensure a given success rate. [ABSTRACT FROM PUBLISHER]
- Subjects :
- GROUP testing
LINEAR programming
SPARSE approximations
TESTING
POPULATION statistics
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 63
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 125813371
- Full Text :
- https://doi.org/10.1109/TIT.2017.2748143