NDLI: Group Testing With Probabilistic Tests: Theory, Design and Application

Content Provider	IEEE Xplore Digital Library
Author	Cheraghchi, M. Hormati, A. Karbasi, A. Vetterli, M.
Copyright Year	1963
Abstract	Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items into different pools and detecting defective members based on the set of test results obtained for each pool. In a classical noiseless group testing setup, it is assumed that the sampling procedure is fully known to the reconstruction algorithm, in the sense that the existence of a defective member in a pool results in the test outcome of that pool to be positive. However, this may not be always a valid assumption in some cases of interest. In particular, we consider the case where the defective items in a pool can become independently inactive with a certain probability. Hence, one may obtain a negative test result in a pool despite containing some defective items. As a result, any sampling and reconstruction method should be able to cope with two different types of uncertainty, i.e., the unknown set of defective items and the partially unknown, probabilistic testing procedure. In this work, motivated by the application of detecting infected people in viral epidemics, we design nonadaptive sampling procedures that allow successful identification of the defective items through a set of probabilistic tests. Our design requires only a small number of tests to single out the defective items. In particular, for a population of size N and at most K defective items with activation probability p, our results show that M = O(K² log (N/K)/p³) tests is sufficient if the sampling procedure should work for all possible sets of defective items, while M = O(K log (N)/p³) tests is enough to be successful for any single set of defective items. Moreover, we show that the defective members can be recovered using a simple reconstruction algorithm with complexity of O(MN).
Sponsorship	IEEE Information Theory Society
Starting Page	7057
Ending Page	7067
Page Count	11
File Size	707819
File Format	PDF
ISSN	00189448
Volume Number	57
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-10-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Testing Sparse matrices Decoding Probabilistic logic Reconstruction algorithms Compressed sensing Uncertainty sparsity recovery epidemiology group testing probabilistic tests
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Vanishingly Sparse Matrices and Expander Graphs, With Application to Compressed Sensing

Semiquantitative Group Testing

Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors

Density Evolution Analysis of Node-Based Verification-Based Algorithms in Compressed Sensing

Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

Sparse Recovery With Graph Constraints

Boolean Compressed Sensing and Noisy Group Testing

Blind Compressed Sensing

Theoretical and Empirical Results for Recovery From Multiple Measurements

Group Testing With Probabilistic Tests: Theory, Design and Application

Similar Documents

Vanishingly Sparse Matrices and Expander Graphs, With Application to Compressed Sensing

Semiquantitative Group Testing

Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors

Density Evolution Analysis of Node-Based Verification-Based Algorithms in Compressed Sensing

Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

Sparse Recovery With Graph Constraints

Boolean Compressed Sensing and Noisy Group Testing

Blind Compressed Sensing

Theoretical and Empirical Results for Recovery From Multiple Measurements

Group Testing With Probabilistic Tests: Theory, Design and Application