Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes
63
0
0.0
(
0
)
Added by
Jonathan Scarlett
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
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.
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.
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
