Abstract | ||
---|---|---|
We consider an efficiently decodable non-adaptive group testing (NAGT) problem that meets theoretical bounds. The problem is to find a few specific items (at most $d$) satisfying certain characteristics in a colossal number of $N$ items as quickly as possible. Those $d$ specific items are called textit{defective items}. The idea of NAGT is to pool a group of items, which is called textit{a test}, then run a test on them. If the test outcome is textit{positive}, there exists at least one defective item in the test, and if it is textit{negative}, there exists no defective items. Formally, a binary $t times N$ measurement matrix $mathcal{M} = (m_{ij})$ is the representation for $t$ tests where row $i$ stands for test $i$ and $m_{ij} = 1$ if and only if item $j$ belongs to test $i$. There are three main objectives in NAGT: minimize the number of tests $t$, construct matrix $mathcal{M}$, and identify defective items as quickly as possible. In this paper, we present a strongly explicit construction of $mathcal{M}$ for when the number of defective items is at most 2, with the number of tests $t simeq 16 log{N} = O(log{N})$. In particular, we need only $K simeq N times 16log{N} = O(Nlog{N})$ bits to construct such matrices, which is optimal. Furthermore, given these $K$ bits, any entry in the matrix can be constructed in time $O left(ln{N}/ ln{ln{N}} right)$. Moreover, $mathcal{M}$ can be decoded with high probability in time $Oleft( frac{ln^2{N}}{ln^2{ln{N}}} right)$. When the number of defective items is greater than 2, we present a scheme that can identify at least $(1-epsilon)d$ defective items with $t simeq 32 C(epsilon) d log{N} = O(d log{N})$ in time $O left( d frac{ln^2{N}}{ln^2{ln{N}}} right)$ for any close-to-zero $epsilon$, where $C(epsilon)$ is a constant that depends only on $epsilon$. |
Year | Venue | Field |
---|---|---|
2017 | arXiv: Information Theory | Discrete mathematics,Combinatorics,Matrix (mathematics),Concatenation,Group testing,Mathematics,Binary number |
DocType | Volume | Citations |
Journal | abs/1701.06989 | 0 |
PageRank | References | Authors |
0.34 | 2 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thach V. Bui | 1 | 21 | 7.65 |
Minoru Kuribayashi | 2 | 23 | 19.55 |
Isao Echizen | 3 | 299 | 68.82 |