Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimum Detection of Defective Elements in Non-Adaptive Group Testing
75
0
0.0
(
0
)
Added by
Gianluigi Liva
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We explore the problem of deriving a posteriori probabilities of being defective for the members of a population in the non-adaptive group testing framework. Both noiseless and noisy testing models are addressed. The technique, which relies of a trellis representation of the test constraints, can be applied efficiently to moderate-size populations. The complexity of the approach is discussed and numerical results on the false positive probability vs. false negative probability trade-off are presented.
rate research
Read More
We consider non-adaptive threshold group testing for identification of up to $d$ defective items in a set of $n$ items, where a test is positive if it contains at least $2 leq u leq d$ defective items, and negative otherwise. The defective items can be identified using $t = O left( left( frac{d}{u} right)^u left( frac{d}{d - u} right)^{d-u} left(u log{frac{d}{u}} + log{frac{1}{epsilon}} right) cdot d^2 log{n} right)$ tests with probability at least $1 - epsilon$ for any $epsilon > 0$ or $t = O left( left( frac{d}{u} right)^u left( frac{d}{d -u} right)^{d - u} d^3 log{n} cdot log{frac{n}{d}} right)$ tests with probability 1. The decoding time is $t times mathrm{poly}(d^2 log{n})$. This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(nlog{n} + n log{frac{1}{epsilon}})$ for probabilistic decoding, where $epsilon > 0$, and $O(n^u log{n})$ for deterministic decoding.
In this paper, we consider the problem of noiseless non-adaptive probabilistic group testing, in which the goal is high-probability recovery of the defective set. We show that in the case of $n$ items among which $k$ are defective, the smallest possible number of tests equals $min{ C_{k,n} k log n, n}$ up to lower-order asymptotic terms, where $C_{k,n}$ is a uniformly bounded constant (varying depending on the scaling of $k$ with respect to $n$) with a simple explicit expression. The algorithmic upper bound follows from a minor adaptation of an existing analysis of the Definite Defectives (DD) algorithm, and the algorithm-independent lower bound builds on existing works for the regimes $k le n^{1-Omega(1)}$ and $k = Theta(n)$. In sufficiently sparse regimes (including $k = obig( frac{n}{log n} big)$), our main result generalizes that of Coja-Oghlan {em et al.} (2020) by avoiding the assumption $k le n^{1-Omega(1)}$, whereas in sufficiently dense regimes (including $k = omegabig( frac{n}{log n} big)$), our main result shows that individual testing is asymptotically optimal for any non-zero target success probability, thus strengthening an existing result of Aldridge (2019) in terms of both the error probability and the assumed scaling of $k$.
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$.
The goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. A test is positive if it has at least $u$ defective items and negative otherwise. Our objective is to identify defective items in sublinear time the number of items, e.g., $mathrm{poly}(d, ln{n}),$ by using the number of tests as low as possible. In this paper, we reduce the number of tests to $O left( h times frac{d^2 ln^2{n}}{mathsf{W}^2(d ln{n})} right)$ and the decoding time to $O left( mathrm{dec}_0 times h right),$ where $mathrm{dec}_0 = O left( frac{d^{3.57} ln^{6.26}{n}}{mathsf{W}^{6.26}(d ln{n})} right) + O left( frac{d^6 ln^4{n}}{mathsf{W}^4(d ln{n})} right)$, $h = Oleft( frac{d_0^2 ln{frac{n}{d_0}}}{(1-p)^2} right)$ , $d_0 = max{u, d - u }$, $p in [0, 1),$ and $mathsf{W}(x) = Theta left( ln{x} - ln{ln{x}} right).$ If the number of tests is increased to $Oleft( h times frac{d^2ln^3{n}}{mathsf{W}^2(d ln{n})} right),$ the decoding complexity is reduced to $O left(mathrm{dec}_1 times h right),$ where $mathrm{dec}_1 = max left{ frac{d^2 ln^3{n}}{mathsf{W}^2(d ln{n})}, frac{ud ln^4{n}}{mathsf{W}^3(d ln{n})} right}.$ Moreover, our proposed scheme is capable of handling errors in test outcomes.
The task of non-adaptive group testing is to identify up to $d$ defective items from $N$ items, where a test is positive if it contains at least one defective item, and negative otherwise. If there are $t$ tests, they can be represented as a $t times N$ measurement matrix. We have answered the question of whether there exists a scheme such that a larger measurement matrix, built from a given $ttimes N$ measurement matrix, can be used to identify up to $d$ defective items in time $O(t log_2{N})$. In the meantime, a $t times N$ nonrandom measurement matrix with $t = O left(frac{d^2 log_2^2{N}}{(log_2(dlog_2{N}) - log_2{log_2(dlog_2{N})})^2} right)$ can be obtained to identify up to $d$ defective items in time $mathrm{poly}(t)$. This is much better than the best well-known bound, $t = O left( d^2 log_2^2{N} right)$. For the special case $d = 2$, there exists an efficient nonrandom construction in which at most two defective items can be identified in time $4log_2^2{N}$ using $t = 4log_2^2{N}$ tests. Numerical results show that our proposed scheme is more practical than existing ones, and experimental results confirm our theoretical analysis. In particular, up to $2^{7} = 128$ defective items can be identified in less than $16$s even for $N = 2^{100}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
