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≤u≤d defective items, and negative otherwise. The defective items can be identified using t=O((du)u(dd-u)d-u(ulogdu+log1)∙d2lognε) tests with probability at least 1- for any ε >0 or t=O((du)u(dd-u)d-ud3logn∙lognd) tests with probability 1. The decoding time is t×poly(d2logn). This result significantly improves the best known results for decoding non-adaptive threshold group testing: O(nlogn+nlog1ε) for probabilistic decoding, where ε >0, and O(nulogn) for deterministic decoding.
1 January 2019 in Journal of Information Processing
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 × N measurement matrix. We have answered the question of whether there exists a scheme such that a larger measurement matrix, built from a given t × N measurement matrix, can be used to identify up to d defective items in time O(t log2 N). In the meantime, a t × N nonrandom measurement matrix with $t = O \left(\frac{d^2 \log_2^2{N}}{(\log_2(d\log_2{N}) - \log_2{\log_2(d\log_2{N})})^2} \right)$ can be obtained to identify up to d defective items in time 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 $4\log_2^2{N}$ using $t = 4\log_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 27 = 128 defective items can be identified in less than 16s even for N = 2100.
13 August 2021 in IEEE Transactions on Information Theory
The basic 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$ . The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell $ defective items, where $0 \leq \ell < u$ , and arbitrary otherwise. This is called threshold group testing. The parameter $g = u - \ell - 1$ is called the gap . In this paper, we focus on the case $g > 0$ , i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$ ; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. Specifically, we present a better exact upper bound on the number of tests for disjunct matrices compared with that in related work. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems.
22 April 2024 in IEEE Transactions on Information Theory
In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple “types” of items. Specifically, we assume that there are multiple disjoint semi-defective sets , and a test is positive if and only if it contains at least one item from each of these sets. The goal is to reliably identify all of the semi-defective sets using as few tests as possible, and we refer to this problem as Concomitant Group Testing (ConcGT). We derive a variety of algorithms for this task, focusing primarily on the case that there are two semi-defective sets. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity (namely, 2 or 3 stages). Both our deterministic adaptive algorithm and our randomized algorithms (non-adaptive or limited adaptivity) are order-optimal in broad scaling regimes of interest, and improve significantly over baseline results that are based on solving a more general problem as an intermediate step (e.g., hypergraph learning).
Given up to |$d$| positive items in a large population of |$n$| items (|$d \ll n$|), the goal of threshold group testing is to efficiently identify the positives via tests, where a test on a subset of items is positive if the subset contains at least |$u$| positive items, negative if it contains up to |$\ell $| positive items and arbitrary (either positive or negative) otherwise. The parameter |$g = u - \ell - 1$| is called the gap. In non-adaptive strategies, all tests are fixed in advance and can be represented as a measurement matrix, in which each row and column represent a test and an item, respectively. In this paper, we consider non-adaptive threshold group testing with consecutive positives in which the items are linearly ordered and the positives are consecutive in that order. We show that by designing deterministic and strongly explicit measurement matrices, |$\lceil \log _{2}{\lceil \frac {n}{d} \rceil } \rceil + 2d + 3$| (respectively, |$\lceil \log _{2}{\lceil \frac {n}{d} \rceil } \rceil + 3d$|) tests suffice to identify the positives in |$O \left ( \log _{2}{\frac {n}{d}} + d \right )$| time when |$g = 0$| (respectively, |$g> 0$|). The results significantly improve the state-of-the-art scheme that needs |$15 \lceil \log _{2}{\lceil \frac {n}{d} \rceil } \rceil + 4d + 71$| tests to identify the positives in |$O \left ( \frac {n}{d} \log _{2}{\frac {n}{d}} + ud^{2} \right )$| time, and whose associated measurement matrices are random and (non-strongly) explicit.