Back to Search
Start Over
Nonadaptive Group Testing Based on Sparse Pooling Graphs
- Source :
- IEEE Transactions on Information Theory. 63:1525-1534
- Publication Year :
- 2017
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2017.
-
Abstract
- An information theoretical analysis of nonadaptive group testing schemes based on sparse pooling graphs is presented. A pooling graph is a bipartite graph for which the adjacency matrix is a pooling matrix. The binary status of the objects to be tested are modeled by independent identically distributed. Bernoulli random variables with probability $p$ . An $(l, r, n)$ -regular pooling graph is a bipartite graph in which the left nodes have degree $l$ , the right nodes have degree $r$ , and $n$ is the number of left nodes. The main contribution of this paper is a direct coding theorem that gives the conditions for the existence of an estimator that can achieve an arbitrarily small probability of error. An estimator is a function that uses observations to infer the state of an object. The direct coding theorem is proved by averaging the upper bound on the probability of the estimation error of the typical set estimator over an $(l, r, n)$ -regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime. These results can provide a concrete benchmark for nonadaptive group testing of existing and emerging detection algorithms over a noiseless system.
- Subjects :
- Discrete mathematics
Typical set
Pooling
Estimator
020206 networking & telecommunications
02 engineering and technology
Library and Information Sciences
01 natural sciences
Upper and lower bounds
Computer Science Applications
010104 statistics & probability
0202 electrical engineering, electronic engineering, information engineering
Bipartite graph
Adjacency matrix
0101 mathematics
Random variable
Information Systems
Mathematics
Sparse matrix
Subjects
Details
- ISSN :
- 15579654 and 00189448
- Volume :
- 63
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Information Theory
- Accession number :
- edsair.doi...........0948ee921d71f097e1f678557d59dc19