Non-Adaptive Group Testing Framework based on Concatenation Code

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 $\mathit{\text{defective}}\mathit{\text{items}}$. The idea of NAGT is to pool a group of items, which is called $\mathit{\text{a}}\mathit{\text{test}}$, then run a test on them. If the test outcome is $\mathit{\text{positive}}$, there exists at least one defective item in the test, and if it is $\mathit{\text{negative}}$, there exists no defective items. Formally, a binary $t \times N$measurementmatrix$$\mathcal{M}$ = (m_{ij})$istherepresentationfor$t$testswhererow$i$standsfortest$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 16\log N=O(N\log 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(\ln N\mathrm{/}\ln \ln N)$. Moreover, $\mathcal{M}$ can be decoded with high probability in time $O\left( \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-ϵ)d$ defective items with $t\simeq 32C(ϵ)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 $ϵ$, where $C(ϵ)$ is a constant that depends only on $ϵ$.