Theoretical Bounds on the Number of Tests in Noisy Threshold Group Testing Frameworks

Abstract

We consider a variant of group testing (GT) models called noisy threshold group testing (NTGT), in which when there is more than one defective sample in a pool, its test result is positive. We deal with a variant model of GT where, as in the diagnosis of COVID-19 infection, if the virus concentration does not reach a threshold, not only do false positives and false negatives occur, but also unexpected measurement noise can reverse a correct result over the threshold to become incorrect. We aim to determine how many tests are needed to reconstruct a small set of defective samples in this kind of NTGT problem. To this end, we find the necessary and sufficient conditions for the number of tests required in order to reconstruct all defective samples. First, Fano’s inequality was used to derive a lower bound on the number of tests needed to meet the necessary condition. Second, an upper bound was found using a MAP decoding method that leads to giving the sufficient condition for reconstructing defective samples in the NTGT problem. As a result, we show that the necessary and sufficient conditions for the successful reconstruction of defective samples in NTGT coincide with each other. In addition, we show a trade-off between the defective rate of the samples and the density of the group matrix which is then used to construct an optimal NTGT framework.

1. Introduction

Group Testing (GT) is a underdetermined problem in [1], and numerous methods have been developed to solve their problems. GT has become relevant in various problems including probabilistic approaches. The expansion of compressive sensing goes back to the fundamental idea of GT because it is an effort to find sparse signals [2,3]. Recently, academia has begun using the GT method as on vital approach to finding confirmed COVID-19 cases, showing this field’s potential importance in these uncertain times [4,5].

The first study for GT was proposed by Dorfman [1]. The background to the emergence of GT is that a large project was conducted in the United States to find soldiers with syphilis during World War II. Syphilis testing of inviduals involves taking a blood sample, then analyzing that to produce a positive or negative result for syphilis in that patient. The syphilis testing carried out at the time was very inefficient since it took a lot of time and money to test all the soldiers one by one [3]. After all, if N soldiers are individually tested for syphilis, N tests are required. Note that the number of soldiers infected with syphilis is very small compared to the total number of soldiers. That is why it is probably inefficient to test every soldier for syphilis one by one, and why the GT technique emerged. The initial GT model was performed in the following way [1]. Several soldiers’ blood samples were randomly selected, and the blood was put into a pool and mixed. Then, the blood pool was checked to see if it activated to syphilis or not. A positive result indicates that at least one of the soldiers in the pool was infected with syphilis. A negative result, on the other hand, indicates that all soldiers in the pool were free of syphilis. GT is attractive because the number of tests can be drastically reduced in the case of fewer soldiers infected with syphilis. After these beginnings, GT has mainly been studied with two different approaches, each forming a field of research of its own. One these fields is how to generate GT models. That is, it is a method of selecting samples to be included in one test pool. The second area is to reconstruct defective samples with as few tests as possible. GT loses its benefits if the requirement for a large number of retests leads to as many tests as the number of tests for individual screening.

For GT, various models have been proposed in consideration of how the test results express positive and negative results and the presence or absence of noise. In general, GT’s test results told us to see if the pool under being tested contains one or more defective samples. That is, a positive or negative result indicates whether at least one of the defective samples in the pool are present. The model called quantitative GT [3] is a generalization framework of GT. The test result of quantitative GT indicates the number of defective samples in the test pool. There is also another GT model called Threshold Group Testing (TGT) [6]. In the TGT model, a test result of a pool is positive or negative as in conventional GT schemes. However, unlike the conventional GT model, the positive result occurs only when the number of defective samples in the pool is greater than a given threshold. Otherwise, the test outcome is negative. The TGT model is used because it can represent situations in which the test result can be different depending on whether it is high or low, such as the COVID-19 virus concentration. A modified GT model in which measurement noise causes false negatives or false positives is also considered.

TGT problems have been dealt with in various fields such as construction of TGT models [7], theoretical analysis of performance [8], and efficient model design [9,10]. However, there have been no studies so far to quantify how much measurement noise affects performance of TGT models. In this paper, we consider a Noisy Threshold Group Testing (NTGT) model. We provide guidelines for designing a NTGT model that is robust and reliable to measurement noise. To this end, a lower bound on the number of tests is derived using Fano’s inequality. We show the trade-off relationship between the sparsity of the group matrix and the defective rate of the signal. And we obtain an upper bound on the probability of an error using the MAP decoding method. We show necessary and sufficient conditions on the number of tests required for finding a set of given defective samples using the lower and upper bounds.

2. Related Work

We look through previous studies and their significance to GT. Then, we will classify each type of problem related to current approaches to GT and consider the issues surrounding these problems. The study of GT first began in 1943 [1]. Dorfman made an effort to find a small number of syphilis-infected soldiers. Dorfman performed the GT with the following procedure. When testing for syphilis, all the soldiers were divided into various groups that were equal in size, then individual testing was only performed on soldiers from the groups that had recoded positive test results. In [1], the optimal group size for a given total number of samples and defective rate was summarized and presented. Later, Sterrett improved the performance by slightly modifying the existing GT method [11]. The main idea of Sterrett’s approach is that once the first positive result is obtained, the remaining untested individuals are put in one large grouped and tested. Other than that, there is no difference between Sterrett’s method and Dorfman’s. If there is a low infection rate, Sterrett’s method is more efficient because most of the samples are normal. A more general GT has been presented in [12], in which several algorithms were developed for finding defective samples when no infection rate exists. The paper [12] also provided a link between information theory and GT, introduced a new application of GT, and discussed the generalization of GT.

GT is classified based on types of defective sample distributions and decoding approaches. A probabilistic model uses the assumption that a defective sample is generated from a given probability distribution. On the other hand, the combinatorial model is an attempt to find defective samples without knowledge of probability distributions [13,14]. A typical example of this model is the minmax algorithm [15]. In [16], the results of improved performance in the combinatorial model were presented. Looking at other classes, the adaptive case is a model in which samples to be included in one pool are not independent of the results of previous tests. The samples to be used for the next round are changed each time based on the results of previous tests. Specifically, the method of selecting samples to be included in the next pool is optimized by using the results obtained from previous tests. Conversely, in the non-adaptive model, all tests are performed at the same time by a sample selection process defined in advance. So in this model, every test is independent of each other. This model offers the advantage of being able to test simultaneously regardless of the test order. When predetermined multiple steps are used, the non-adaptive model is extended to multi-stage models [1,17]. In fact, although the adaptive model has more constraints in GT design than the non-adaptive model, the adaptive model generally outperforms the non-adaptive model [3]. However, the recent research in [18] showed limitations in improving the performance of the adaptive model. Non-adaptive GTs are more efficient if all tests are being performed at the same time.

We now look at the significance of certain recent studies on noisy GT. The work in [19] showed the information-theoretic performance of GT with and without measurement noise. Several studies have recently showed interesting and significant performance. In [17], the proposed algorithms uses positive rates in the group to be included for each sample. In this case, if it is greater than the set value, the sample is considered as defective. This approach does not lead to optimal performance in all domains, but it follows a scaling law for a specific domain. In [19], there is separate testing for signals, and all of the group testing is carried out while still considering each sample. That is, although no individual testing is performed, samples use a binary value such as positive or negative. In the case of samples affected by symmetric noise, it was shown that the minimum number of tests reduces to a proportional to $K\log N$ of the optimal information-theoretic bounds for identifying any K defectives samples in a population of N samples [19].

In [20,21], for noisy addition, GT algorithms were presented using message passing and linear programming. Although it does not guarantee optimal performance for decoding complexity, the algorithm proposed in [22] is capable of realistic runtime in terms of that case of a large population. Although many studies have been performed on the noiseless version of GT models, it has been considered as an assumption that the test results are always pure. But this is not realistic. In addition, most of the noisy GT approaches to deal with measurement noise were performed by considering the symmetric noise model such as binary symmetric channel mentioned in channel coding theory. The symmetric noise model referred to in this paper assumes that the test results have the same probability of occurrence of false negatives and false positives. However, asymmetric noise models are more natural than symmetric ones in various applications. For example, data forensics in [23] is an example of using noisy GT models where it identifies to see if recoded files are changed.

3. Noisy Threshold Group Testing Framework

3.1. Problem Statement

We define our NTGT problem. Let be the input $\mathbf{x}$ expressed as a binary vector of size N, $\mathbf{x}=\left(x_1,x_2,\cdots ,x_N\right)$, $\mathbf{x}\in {\left\{0,1\right\}}^N$. For $i\in \left[N\right]$, $x_i$ is the i-th element of $\mathbf{x}$. $x_i$ is expressed in binary to identify either a defective sample or a normal sample. In other words, if the i-th sample is defective, $x_i=1$, otherwise $x_i=0$. Throughout this work, we assume that $x_i$ has the following probability,

$$\mathrm{Pr}\left(x_i=\alpha \right)=\left\{\begin{array}{cc}1-\delta & \mathrm{if}\alpha =0,\\ \delta & \mathrm{if}\alpha =1,\end{array}\right.$$

(1)

where $\delta$ is the defective sample rate, and $\alpha$ is a dummy variable. In this case, the defective sample rate is less than 0.5, 0 $<\delta <$ 0.5, which is considered a small value for GT problems.

As mentioned earlier, one of the key points in the GT problems is to determine which samples to participate in a pool. In this paper, samples to be included in the pool are selected using a non-adaptive model. We use a matrix as a more concise way to define the samples to be included in the pool. Let be the group matrix which has M rows and N columns as denoted $\mathbf{A}\in {\left\{0,1\right\}}^{M\times N}$, where M is the number of tests in the NTGT model. Note that we aim for a small M as the number of tests required to reconstruct the signal $\mathbf{x}$. When the j-th test includes i-th sample $x_i$ and performs GT, it is expressed as $A_{ji}=1$. Otherwise, $A_{ji}=0$. Whether i-th sample is included in the j-th test and performs GT, is expressed as a binary value, i.e., 0 or 1, of each element $A_{ji}$ of the group matrix. Although the d-Separable matrix and the d-Disjunct matrix [3] were used to design the group matrix, the approach of randomly selecting the elements of the group matrix is also known to be a good design method [3]. For $i\in \left[N\right]$ and $j\in \left[M\right]$, $A_{ji}$ is identically independent distributed as follows:

$$\mathrm{Pr}\left(A_{ji}=\alpha \right)=\left\{\begin{array}{cc}1-\gamma & \mathrm{if}\alpha =0,\\ \gamma & \mathrm{if}\alpha =1,\end{array}\right.$$

(2)

where $\gamma$ denotes the sparsity of the group matrix and the range of $\gamma$ is $0<\gamma <1$. As $\gamma$ increases, the density of the group matrix also increases. Conversely, as they get smaller, increasingly sparse group matrices are designed. It should be noted that the computational complexity of the GT framework also increases when a group matrix is constructed from a large $\gamma$. Therefore, it is necessary to design GT frameworks with as low as possible the sparsity of group matrices while improving the reconstruction performance. We will consider how the relationship between $\delta$ and $\gamma$ affects the number of tests for signal reconstruction.

The reason we are considering the NTGT model is as follows. Consider a model that could be used for the diagnosis of COVID-19 infection. There are cases in which the COVID-19 test showed false positive or false negative results when the concentration of the virus was low or contaminated. The current diagnosis of COVID-19 infection is positive when the virus concentration is above a certain level. During the incubation period or early stage of infection, the virus concentration is low, and false negative results may be obtained. In addition, even if the COVID-19 infection is confirmed using a precise and accurate diagnostic method, the result is sometimes reversed due to unexpected measurement noise. Throughout this work, a NTGT model suited to these challenges is considered. In other words, we consider the best approach to a TGT scheme where positive and negative cases occur by the quatitative concentration, and we consider an additive noise model because measurement noise can reverse the results. In a recent study [24], for the diagnosis of COVID-19 infection, false positives and false negatives were reported to be between 0.1% and 4.5%, respectively. Next, we obtain lower and upper performance bounds on the NTGT model in Section 4 and Section 5.

TGT is different from conventional GT models. In conventional GT, if at least one defective sample exists in one test, the output is positive without measurement noise. However, TGT is positive when there is a number of defective samples greater than the predefined threshold T. For example, $T=3$ means that a positive result occurs only when there are at least three defective samples in the pool. Once there is only one defective sample in the pool, its result would be negative. In other words, the result in the pool becomes positive only when it is above T for TGT models, also whether it is negative or positive in the diagnosis of COVID-19 infection depends on whether the virus concentration is high or low. The conventional GT uses $T=1$. The following (3) presents an output for a TGT model. Let $z_j$ be the result of the j-th test pool, which does not suffer from noise, where $z_j=1$ indicates a positive result and 0 for a negative result, $j\in \left[M\right]$, $\mathbf{z}=\left(z_1,z_2,\cdots ,z_M\right)$.

$$z_j=\left\{\begin{array}{cc}0& \mathrm{if}\sum _{i=1}^N{A}_{ji}{x}_i<T,\\ 1& \mathrm{if}\sum _{i=1}^N{A}_{ji}{x}_i\ge T,\end{array}\right.$$

(3)

Through this paper, we consider the NTGT framework with measurement noise. Assume a model whose results can be flipped due to the measurement noise. $z_j$ is the pure result of the pool test, and its result converts from positive to negative and vice versa due to additive noise. For the NTGT model, the additive noise is defined as follows:

$$\mathrm{Pr}\left(e_j=\alpha \right)=\left\{\begin{array}{cc}1-\eta & \mathrm{if}\alpha =0,\\ \eta & \mathrm{if}\alpha =1,\end{array}\right.$$

(4)

where $\eta$ is the measurement noise, and we assume all $e_j$ are independent of each other. Therefore, the j-th output $y_j$ in the NTGT model can be written as

$$y_j=z_j\oplus e_j$$

(5)

where the symbol ⊕ denotes the logical operation XOR. We denote $\mathbf{y}=\left(y_1,y_2,\cdots ,y_M\right)$ and $\mathbf{e}=\left(e_1,e_2,\cdots ,e_M\right)$.

Figure 1 shows an example of this NTGT. In this example, two samples out of ten are defective, which is realized from (1). As shown in Figure 1, the number of tests is 7, $M=7$. The $7\times 10$ group matrix is constructed by (2) mentioned above. For noiseless version, the vector $\mathbf{z}$ is $\left(0,0,1,0,0,0,0\right)$ with $T=2$. In the third test only, the number of defective samples becomes two, and the test result is positive. When additive noise is added as defined in (4), the output is $\mathbf{y}=\left(1,0,1,0,0,0,0\right)$.

3.2. Decoding

We use a maximum a posteriori (MAP) method to reconstruct a signal $\mathbf{x}$ in the NTGT.

$$\widehat{\mathbf{x}}=\arg \underset{\mathbf{x}}{\max }P\left(\left.\mathbf{x}\right|\mathbf{y},\mathbf{A}\right)$$

(6)

The posteriori probability in (6) is as follows:

$$\begin{array}{cc}\hfill P\left(\left.\mathbf{x}\right|\mathbf{y},\mathbf{A}\right)& =\frac{P\left(\mathbf{x},\mathbf{y},\mathbf{A}\right)}{P\left(\mathbf{y},\mathbf{A}\right)}\hfill \\ \hfill & \propto P\left(\mathbf{x},\mathbf{y},\mathbf{A}\right)\hfill \\ \hfill & =\sum _{\mathbf{e}}P\left(\mathbf{x},\mathbf{y},\mathbf{A},\mathbf{e}\right)\hfill \\ \hfill & =\sum _{\mathbf{e}}P\left(\mathbf{x}\right)P\left(\mathbf{A}\right)P\left(\mathbf{e}\right)P\left(\left.\mathbf{y}\right|\mathbf{x},\mathbf{A},\mathbf{e}\right)\hfill \end{array}$$

(7)

The last line of (7) is obtained using independent conditions, while the conditional probability $P\left(\left.\mathbf{y}\right|\mathbf{x},\mathbf{A},\mathbf{e}\right)$ is an indicator function that satisfies the following condition:

$$P\left(\left.\mathbf{y}\right|\mathbf{x},\mathbf{A},\mathbf{e}\right)=\left\{\begin{array}{cc}1& \mathrm{if}\mathbf{y}=\mathbf{z}\oplus \mathbf{e},\\ 0& \mathrm{if}\mathbf{y}\ne \mathbf{z}\oplus \mathbf{e},\end{array}\right.$$

(8)

We define an error event if $\widehat{\mathbf{x}}$ from (6) is not the same as the true realization of $\mathbf{x}$. In other words, the probability of an error is expressed as $P_E=\mathrm{Pr}\left\{\widehat{\mathbf{x}}\ne \mathbf{x}\right\}$.

3.3. Bounds for Group Testing Schemes

Now consider the number of tests on successful decoding in the conventional GT models. The number of tests required to identify K defective samples out of all N samples for an adaptive GT algorithm with perfect reconstruction denotes as $m\left(N,K\right)$. Moreover, for the case of a non-adaptive model, the number of tests is defined as $\overline{m}\left(N,K\right)$. The number of tests N required for individual testing is greater than $\overline{m}\left(N,K\right)$. Adaptive GT models require less or equal number of tests than those of non-adaptive GTs because they check the results of previous tests and perform the next tests, $m\left(N,K\right)\le \overline{m}\left(N,K\right)$. Even if the number of defective samples is one, at least one test must be performed, $1\le m\left(N,K\right)$. Therefore, the number of tests has a wide range as follows:

$$1\le m\left(N,K\right)\le \overline{m}\left(N,K\right)\le N$$

(9)

From an information-theoretic bound, the minimum number of tests M for a GT framework with a sample space is obtained as [3],

$$M\ge {\log }_2\left|\mathcal{S}\right|$$

(10)

where $\mathcal{S}$ denotes the sample space. In addition, an information-theoretic performance is presented even for a GT framework with small error probability. It is expressed as an upper bound of the error probability for the number of tests required for successful decoding. This GT algorithm performs in such a way as the following bound on successful probability $P_s$ for decoding of defective samples [25]:

$$P_s\le \frac{M}{{\log }_2\left(\genfrac{}{}{0pt}{}{N}{K}\right)}$$

(11)

In the past half century, many studies on GT models have been performed, and among them, well-known and important GT algorithms are introduced next. The first one to be considered is the binary splitting algorithm [3]. This algorithm solves the existing GT problems efficiently and is applicable to the adaptive GT models. So far, the reason this algorithm is used for GT problems is because of its simplicity and good performance. The number of tests required to reconstruct defective samples using the binary splitting algorithm is known through the following bounds:

$$M=\left\{\begin{array}{cc}N& \mathrm{if}N\le 2K-2,\\ \left({\log }_2\sigma +2\right)K+p-1& \mathrm{if}N\ge 2K-1,\end{array}\right.$$

(12)

where $\sigma$ is the number of samples to be included for one test, and p is a uniquely determined nonnegative integer conditioning $p<K$.

Next, the definite defectives algorithm [26] is considered. This algorithm is suitable for non-adaptive GT models because an unknown input signal can be reconstructed using all of the test results at the same time through an iterative process. The feature of the definite defectives algorithm is attractive in that it can eliminate false negatives that may occur during the reconstruction process. As a result, the use of the definite defectives algorithm is more useful in applications where false negatives are sensitive or should not be present. For given N and K, the definite defective algorithm has the following lower bound for the number of tests M required for identifying defective samples if it is allowed an error rate of $\sigma$,

$$M\ge \left(1-\sigma \right){\log }_2\left(\genfrac{}{}{0pt}{}{N}{K}\right)$$

(13)

This can be observed that (11) and (13) coincide with the same in the perfect reconstruction of defective samples.

4. Necessary Condition for Complete Recovery

4.1. Lower Bound

In this section, we take into account a necessary condition for the number of tests required to identify defective samples in the NTGT model. We obtain the necessary condition using Fano’s inequality theorem [27] presented in information theory. Fano’s inequality is mainly exploited in channel coding theory, and describes the connection between error probability and entropy. In addition, in [28], the authors reviewed GT problems comprehensively and in-depth from an information theory perspective. The lower bound on the probability of an error is obtained by considering Fano’s inequality theorem. From this lower bound, we are lead to the necessary condition for the number of tests to find all defective samples for the NTGT model. We first explain Fano’s inequality theorem before deriving the necessary condition.

Theorem 1 

(Fano’s inequality [27]). Suppose there are random variables A and B of finite size. If the decoding function Φ that finds A by considering B is used, the following inequality holds:

$$1+P\left(\mathsf{\Phi }\left(B\right)\ne A\right){\log }_2\left|A\right|\ge H\left(A\left|B\right.\right)$$

(14)

where $P\left(\mathsf{\Phi }\left(B\right)\ne A\right)$ is the probability of an error for the decoding function Φ, and the conditional entropy $H\left(A\left|B\right.\right)$ is defined as follows:

$$H\left(A\left|B\right.\right)=-\sum _{\alpha \in A}\sum _{\beta \in B}{P}_{AB}\left(\alpha ,\beta \right)\log P_{A\left|B\right.}\left(\alpha \left|\beta \right.\right)$$

(15)

where $P_{AB}$ and $P_{A\left|B\right.}$ are the joint probability and conditional probability, respectively.

In the NTGT problem, we are able to obtain a lower bound on the probability of an error. This lower bound shows the minimum number of tests required to reconstruct an unknown signal, regardless of which decoding function is used. In this paper, our lower bound is a variant of the results obtained in [8]. Compared to [8], this work obtains the lower bound taking into account the measurement noise. However, the overall procedure of derivation is similar to each other because it uses Fano’s inequality theorem.

Theorem 2 

(Lower bound). For any decoding function with the unknown sample signal defined in (1) and the measurement noise defined in (4), a necessary condition for the probability of error $P_E$ to be less than an arbitrary small and positive value ρ for $P_E<\rho$ holds such that

$$\frac{NH\left(\delta \right)-M+MH\left(\eta \right)-1}{N}<\rho$$

(16)

where $H\left(·\right)$ is the entropy function.

Proof of Theorem 2.

Let $\widehat{\mathbf{x}}$ be the estimated signal of $\mathbf{x}$ found using the decoding function. Considering the following process in terms of a Markov chain, we can say $\mathbf{x}\to \left(\mathbf{y},\mathbf{A}\right)\to \widehat{\mathbf{x}}$. Then, the following inequality is satisfied,

$$H\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)\le H\left(\mathbf{x}\left|\widehat{\mathbf{x}}\right.\right)$$

(17)

Further, from Fano’s inequality described in (14), the conditional entropy is bounded by

$$H\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)\le 1+P_E{\log }_2\left(2^N-1\right)$$

(18)

Then, the probability of error is bounded in terms of the conditional entropy and the total number of samples N,

$$P_E\ge \frac{H\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)-1}{N}$$

(19)

It needs to tackle the conditional entropy $H\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)$. Let us divide and expand the following conditional entropy in more detail:

$$\begin{array}{ccc}\hfill H\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)& =& H\left(\mathbf{x}\right)-I\left(\mathbf{x};\mathbf{y},\mathbf{A}\right)\hfill \\ \hfill & =& H\left(\mathbf{x}\right)-\left(I\left(\mathbf{x};\mathbf{A}\right)+I\left(\mathbf{x};\mathbf{y}\left|\mathbf{A}\right.\right)\right)\hfill \\ \hfill & \stackrel{\left(a\right)}{=}& H\left(\mathbf{x}\right)-\left(H\left(\mathbf{y}\left|\mathbf{A}\right.\right)-H\left(\mathbf{y}\left|\mathbf{A},\mathbf{x}\right.\right)\right)\hfill \end{array}$$

(20)

where $I\left(·\right)$ is mutual information, and equality (a) comes from the fact that $\mathbf{x}$ and $\mathbf{A}$ are independent of each other. Note that the smaller the term on the right side of (19), the lower the minimum value of the probability of error. This means that the conditional entropy, $H\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)$, should be small as possible. As a result, on the last line of the right side in (20), the conditional entropy $H\left(\mathbf{y}\left|\mathbf{A}\right.\right)$ should be large; conversely, the conditional entropy $H\left(\mathbf{y}\left|\mathbf{A},\mathbf{x}\right.\right)$ should be small.

To do this, let us find the maximum and minimum values of the two conditional entropies, respectively.

$$\begin{array}{ccc}\hfill H\left(\mathbf{y}\left|\mathbf{A}\right.\right)\le H\left(\mathbf{y}\right)& =& H\left(\mathbf{z}\oplus \mathbf{e}\right)\hfill \\ \hfill & \le & M\hfill \end{array}$$

(21)

where the first inequality is due to the definition of conditional entropy, and the last inequality comes from the fact that the result $y_j$ is either 0 or 1, $y_j$ values are independent of each other, and the maximum binary entropy is 1 in the case that $\mathrm{Pr}\left(y_j=0\right)=\mathrm{Pr}\left(y_j=1\right)$. Next, we take into account the other conditional entropy $H\left(\mathbf{y}\left|\mathbf{A},\mathbf{x}\right.\right)$ which is minimized,

$$\begin{array}{ccc}\hfill H\left(\mathbf{y}\left|\mathbf{A},\mathbf{x}\right.\right)& =& H\left(\mathbf{z}\oplus \mathbf{e}\left|\mathbf{A},\mathbf{x}\right.\right)\hfill \\ \hfill & =& H\left(\mathbf{e}\right)\hfill \\ \hfill & =& MH\left(\eta \right)\hfill \end{array}$$

(22)

where the second equality comes from how the randomness of $\mathbf{z}$ vanishes if $\mathbf{x}$ and $\mathbf{A}$ are known, the last equality being due to the independent events of $\mathbf{e}$. Using (21) and (22), (20) can be rewritten as

$$H\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)\le NH\left(\delta \right)-M+MH\left(\eta \right)$$

(23)

Finally, if (19) is changed to satisfy the condition $P_E<\rho$ where $\rho$ is a small, positive value and $\rho >0$, the following condition holds:

$$\frac{NH\left(\delta \right)-M+MH\left(\eta \right)-1}{N}<\rho$$

(24)

This completes the proof of Theorem 2. □

4.2. Construction of Noisy Threshold Group Testing

We now consider the result obtained from Theorem 2. First, Theorem 2 can be expressed as the ratio of the number of tests to the total number of samples as follows:

$$\frac{M}{N}>\frac{H\left(\delta \right)-\rho }{1-H\left(\eta \right)}$$

(25)

It is advantageous to use the NTGT framework until the point N and M are equal. Otherwise, when $M>N$, individual testing becomes more effective than GT. This shows that NTGT can theoretically be used under the following noise conditions:

$$H\left(\eta \right)<1+\rho -H\left(\delta \right)$$

(26)

To design an NTGT framework, how to construct a group matrix is important. The key to this is shown in the proof of Theorem 2. Looking carefully at the conditions under which the inequality of conditional entropy holds in (21), the maximum conditional entropy $H\left(\mathbf{y}\left|\mathbf{A}\right.\right)$ is obtained when the following conditions are satisfied: $\mathrm{Pr}\left(y_j=0\right)=\mathrm{Pr}\left(y_j=1\right)$. This means that the NTGT system should be designed so that the output has an equal probability of being 0 or 1. Since $\mathbf{x}$ and $\mathbf{A}$ are independent of each other, the probability of an output of 0 is as follows:

$$\mathrm{Pr}\left(y_j=0\right)=\sum _{t=0}^{T-1}\left(\genfrac{}{}{0pt}{}{N}{t}\right){\left(\delta \gamma \right)}^t{\left(1-\delta \gamma \right)}^{N-t}=\frac{1}{2}$$

(27)

As shown in (27), it can be seen that there is a trade-off between $\delta$ and $\gamma$. In other words, to reconstruct a sparse signal, a high-density group matrix needs to be generated and used. Conversely, if the signal is not sparse, the group matrix should be designed with low density.

5. Sufficient Condition for Average Performance

5.1. Upper Bound

Now we prove there is an upper bound on the probability of errors from the MAP decoding used in NTGT. We divide the proof of the upper bound into two parts: one considers the definition of the error event and the other part formulates the probability of errors.

We rewrite the a posteriori probability.

$$P\left(\mathbf{x}\left|\mathbf{y},\mathbf{A}\right.\right)\propto \sum _{\mathbf{e}}P\left(\mathbf{x}\right)P\left(\mathbf{A}\right)P\left(\mathbf{e}\right)1_{\mathbf{y}=\mathbf{z}\oplus \mathbf{e}}$$

(28)

Note that both $\mathbf{A}$ and $\mathbf{y}$ are given and known. Using MAP decoding, we estimate with (28)

$$\widehat{\mathbf{x}}=\arg \underset{\mathbf{x}}{\max }\sum _{\mathbf{e}}P\left(\mathbf{x}\right)P\left(\mathbf{A}\right)P\left(\mathbf{e}\right)1_{\mathbf{y}=\mathbf{z}\oplus \mathbf{e}}$$

(29)

An error event occurs if there is a feasible vector $\overline{\mathbf{x}}\ne \mathbf{x}$, such that

$$\sum _{\mathbf{v}}P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)1_{\mathbf{y}=\mathbf{w}\oplus \mathbf{v}}\ge \sum _{\mathbf{e}}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)1_{\mathbf{y}=\mathbf{z}\oplus \mathbf{e}}$$

(30)

where $\mathbf{w}={\sum }_{A_{ji}{\overline{x}}_i\ge T}\mathbf{A}\overline{\mathbf{x}}$ comes from (3), and $\mathbf{v}$ comes from a realization from (4). When given $\mathbf{y}$, $\mathbf{A}$, and $\mathbf{x}$, we have one vector $\mathbf{e}$, such that $\mathbf{e}=\mathbf{z}\oplus \mathbf{y}$. Then we can rewrite (30).

$$P\left(\overline{\mathbf{x}}\right)P_{\mathbf{v}}\left(\mathbf{y}\oplus \mathbf{w}\right)\ge P\left(\mathbf{x}\right)P_{\mathbf{e}}\left(\mathbf{y}\oplus \mathbf{z}\right)$$

(31)

Therefore, an error event becomes equivalent to there existing a pair $\left(\overline{\mathbf{x}},\mathbf{v}\right)$ such that

$$\begin{array}{c}\overline{\mathbf{x}}\ne \mathbf{x},\\ \mathbf{y}=\mathbf{w}\oplus \mathbf{v}=\mathbf{z}\oplus \mathbf{e},\\ P\left(\overline{\mathbf{x}}\right)P_{\mathbf{v}}\left(\mathbf{y}\oplus \mathbf{w}\right)\ge P\left(\mathbf{x}\right)P_{\mathbf{e}}\left(\mathbf{y}\oplus \mathbf{z}\right)\end{array}$$

(32)

So far, we have defined the error event and now we will derive an upper bound on the probability of error. When given $\mathbf{x}$ and $\mathbf{e}$, we let $P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)$ be the conditional error probability. We have an average error probability as follows:

$$P_E=\sum _{\mathbf{x}}\sum _{\mathbf{e}}P\left(\mathbf{x},\mathbf{e}\right)P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)$$

(33)

We now introduce two typical sets that were defined in [27] (Ch.3.1). Let ${\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M$ and ${\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N$ be typical sets of $\mathbf{x}$ and $\mathbf{e}$ with respect to $P\left(\mathbf{x}\right)$ and $P\left(\mathbf{e}\right)$ as defined in (1) and (4). For any positive number $\epsilon$ and sufficiently large numbers of N and M, the two typical sets are defined as

$${\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N=\left\{\mathbf{x}\in 2^N:\left|-\frac{1}{N}\log P\left(\mathbf{x}\right)-H\left(\delta \right)\right|\le \epsilon \right\}$$

(34)

and

$${\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M=\left\{\mathbf{e}\in 2^M:\left|-\frac{1}{M}\log P\left(\mathbf{e}\right)-H\left(\eta \right)\right|\le \epsilon \right\}$$

(35)

From the Shannon–McMillan–Breiman theorem [27] (Ch.16.8), we obtain the following two bounds:

$$P\left(\left|-\frac{1}{N}\log P\left(\mathbf{x}\right)-H\left(\delta \right)\right|\le \epsilon \right)\ge 1-\epsilon$$

(36)

and

$$P\left(\left|-\frac{1}{M}\log P\left(\mathbf{e}\right)-H\left(\eta \right)\right|\le \epsilon \right)\ge 1-\epsilon$$

(37)

Now we define the space of the pair $\left(\mathbf{x},\mathbf{e}\right)$ with respect to the two typical sets. Let $\mathcal{U}$ and ${\mathcal{U}}^c$ be the sets for the pair $\left(\mathbf{x},\mathbf{e}\right)$ such that

$$\mathcal{U}=\left\{\mathbf{x}\in 2^N,\mathbf{e}\in 2^M:\left(\mathbf{x}\in {\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N\bigcap \mathbf{e}\in {\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M\right)\right\}$$

(38)

and

$${\mathcal{U}}^c=\left\{\mathbf{x}\in 2^N,\mathbf{e}\in 2^M:\left(\mathbf{x}\notin {\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N\bigcup \mathbf{e}\notin {\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M\right)\right\}$$

(39)

where $\mathcal{U}$ is the joint typical set for the pair $\left(\mathbf{x},\mathbf{e}\right)$, since $\mathbf{x}$ and $\mathbf{e}$ are independent.

Theorem 3 

(Upper bound). In NTGT one, a distribution of defective samples defined in (1) and noise probability defined in (4), for any small ε, the ratio of the number of tests M to the total number of samples N is upper-bounded:

$$\frac{M}{N}>\frac{H\left(\delta \right)+\epsilon }{1-H\left(\eta \right)-\epsilon }$$

(40)

Proof of Theorem 3.

The probability of error is bounded as

$$\begin{array}{cc}\hfill P_E& =\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)+\sum _{\left(\mathbf{x},\mathbf{e}\right)\in {\mathcal{U}}^c}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)\hfill \\ \hfill & \stackrel{\left(a\right)}{\le }\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)+\sum _{\left(\mathbf{x},\mathbf{e}\right)\in {\mathcal{U}}^c}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)\hfill \\ \hfill & \stackrel{\left(b\right)}{\le }\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)+2\epsilon \hfill \end{array}$$

(41)

where (a) is due to $P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)\le 1$, and (b) comes from the following,

$$\begin{array}{cc}\hfill \sum _{\left(\mathbf{x},\mathbf{e}\right)\in {\mathcal{U}}^c}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)& =1-\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)\hfill \\ \hfill & =1-\sum _{\mathbf{x}\notin {\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N}P\left(\mathbf{x}\right)\sum _{\mathbf{e}\notin {\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M}P\left(\mathbf{e}\right)\hfill \\ \hfill & \le 1-\left(1-\epsilon \right)\left(1-\epsilon \right)\hfill \\ \hfill & \le 2\epsilon \hfill \end{array}$$

(42)

This is because $\mathbf{A}$ is randomly generated as defined in (2); then we can define the following event as

$$\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)=\left\{\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right):\mathbf{z}\oplus \mathbf{e}=\mathbf{w}\oplus \mathbf{v}\right\}$$

(43)

The conditional error probability $P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)$ is the probability of the union of all the events in (43) with respect to all pairs $\left(\overline{\mathbf{x}},\mathbf{v}\right)$ that satisfy (32). Thus, the conditional error probability in (33) can be rewritten as

$$P\left(\mathcal{I}\left|\mathbf{x},\mathbf{e}\right.\right)=\mathrm{Pr}\left\{\bigcup _{\overline{\mathbf{x}},\mathbf{v}:P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)\ge P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)}\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)\right\}$$

(44)

Using the union bound in (41), we have the following bound:

$$\begin{array}{cc}\hfill P_E& \le \sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)\sum _{\left(\overline{\mathbf{x}},\mathbf{v}\right):P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)\ge P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)}P\left(\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)\right)+2\epsilon \hfill \\ \hfill & =\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)\sum _{\left(\overline{\mathbf{x}},\mathbf{v}\right)}P\left(\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)\right)\mathsf{\Phi }\left(\mathbf{x},\overline{\mathbf{x}},\mathbf{e},\mathbf{v}\right)+2\epsilon \hfill \end{array}$$

(45)

where $\mathsf{\Phi }\left(\mathbf{x},\overline{\mathbf{x}},\mathbf{e},\mathbf{v}\right)$ is the indicator function, such that $P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)\ge P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)$.

$$\mathsf{\Phi }\left(\mathbf{x},\overline{\mathbf{x}},\mathbf{e},\mathbf{v}\right)=\left\{\begin{array}{c}1\mathrm{if}P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)\ge P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)\hfill \\ 0\mathrm{if}P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)<P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)\hfill \end{array}\right.$$

(46)

The indicator function is bounded [29] (Ch. 5.6) for $0<s\le 1$.

$$\mathsf{\Phi }\left(\mathbf{x},\overline{\mathbf{x}},\mathbf{e},\mathbf{v}\right)\le {\left(\frac{P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)}{P\left(\mathbf{x}\right)P\left(\mathbf{e}\right)}\right)}^s$$

(47)

For $s=1$ in (47), we have the following bound:

$$P_E\le \sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}\sum _{\left(\overline{\mathbf{x}},\mathbf{v}\right)}P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)P\left(\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)\right)+2\epsilon$$

(48)

From the definition in (43), note that the probability $P\left(\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)\right)$ is

$$P\left(\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)\right)=\mathrm{Pr}\left(\mathbf{w}\oplus \mathbf{v}=\mathbf{z}\oplus \mathbf{e}\right)$$

(49)

where

$$\begin{array}{cc}\hfill P_E& \le \sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U}}\sum _{\left(\overline{\mathbf{x}},\mathbf{v}\right)}P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)P\left(\mathcal{E}\left(\mathbf{x},\mathbf{e};\overline{\mathbf{x}},\mathbf{v}\right)\right)+2\epsilon \hfill \\ \hfill & =\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U},{∥\mathbf{e}\oplus \mathbf{v}∥}_0=d_2}\sum _{{∥\overline{\mathbf{x}}∥}_0=d_1}\sum _{{∥\mathbf{e}\oplus \mathbf{v}∥}_0=d_2}P\left(\overline{\mathbf{x}}\right)P\left(\mathbf{v}\right)P(\mathbf{z}\oplus \mathbf{w}=\mathbf{e}\oplus \mathbf{v}|{∥\overline{\mathbf{x}}∥}_0=d_1,{∥\mathbf{e}\oplus \mathbf{v}∥}_0=d_2)\hfill \end{array}$$

(50)

In (50), we find the following probability depending on the number of nonzero elements $d_1$ and $d_2$:

$$\begin{array}{cc}\hfill P(\mathbf{z}\oplus \mathbf{w}=\mathbf{e}\oplus \mathbf{v}|{∥\overline{\mathbf{x}}∥}_0=d_1,{∥\mathbf{e}\oplus \mathbf{v}∥}_0=d_2)& =\prod _{j=1}^{M}P(z_j\oplus w_j=e_j\oplus v_j|{∥\overline{\mathbf{x}}∥}_0=d_1,{∥\mathbf{e}\oplus \mathbf{v}∥}_0=d_2)\hfill \\ \hfill & =P(z_j\oplus w_j=1|{∥\overline{\mathbf{x}}∥}_0=d_1,{∥\mathbf{e}\oplus \mathbf{v}∥}_0=d_2{)}^{d_2}\hfill \\ \hfill & \times P(z_j\oplus w_j=0|{∥\overline{\mathbf{x}}∥}_0=d_1,{∥\mathbf{e}\oplus \mathbf{v}∥}_0=d_2{)}^{M-d_2}\hfill \\ \hfill & ={\left(1-P_0\right)}^{d_2}{P}_0^{M-d_2}\hfill \end{array}$$

(51)

where each row is independent. Given this, we define the following probability:

$$P_0\stackrel{\Delta }{=}\mathrm{Pr}\left(z_j\oplus w_j=0\left|{∥\overline{\mathbf{x}}∥}_0=d_1\right.\right)$$

(52)

We can divide $P_0$ in (52) into two parts. If $d_1<T$,

$$\begin{array}{cc}\hfill P_0& =\mathrm{Pr}\left(z_j=0\right)\mathrm{Pr}\left(w_j=0\right)+\mathrm{Pr}\left(z_j=1\right)\mathrm{Pr}\left(w_j=1\right)\hfill \\ & =\mathrm{Pr}\left(z_j=0\right)\hfill \end{array}$$

(53)

Otherwise,

$$\begin{array}{cc}\hfill P_0& =\mathrm{Pr}\left(z_j=0\right)\left(\sum _{t=0}^{T-1}\left(\genfrac{}{}{0pt}{}{d_1}{t}\right){\gamma }^t{\left(1-\gamma \right)}^{\left(d_1-t\right)}\right)+\mathrm{Pr}\left(z_j=1\right)\left(\sum _{t=T}^{d_1}\left(\genfrac{}{}{0pt}{}{d_1}{t}\right){\gamma }^t{\left(1-\gamma \right)}^{\left(d_1-t\right)}\right)\hfill \\ \hfill & =P_{z,0}\left(\delta ,\gamma \right)P_{w,0}\left(d_1,\gamma \right)+\left(1-P_{z,0}\left(\delta ,\gamma \right)\right)\left(1-P_{w,0}\left(d_1,\gamma \right)\right)\hfill \end{array}$$

(54)

where

$$\begin{array}{c}\hfill P_{z,0}\left(\delta ,\gamma \right)\stackrel{\Delta }{=}\mathrm{Pr}\left(z_j=0\right)=\sum _{t=0}^{T-1}\left(\genfrac{}{}{0pt}{}{N}{t}\right){\left(\delta \gamma \right)}^t{\left(1-\delta \gamma \right)}^{N-t},\\ \hfill P_{w,0}\left(d_1,\gamma \right)\stackrel{\Delta }{=}\mathrm{Pr}\left(w_j=0\right)=\sum _{t=0}^{T-1}\left(\genfrac{}{}{0pt}{}{d_1}{t}\right){\gamma }^t{\left(1-\gamma \right)}^{d_1-t}\end{array}$$

(55)

The maximum for $P_0$ by looking at $P_{z,0}\left(\delta ,\gamma \right)=1/2$ and $P_{w,0}\left(d_1,\gamma \right)=1/2$ from the fact that $P_0$ in (54) is concave with respect to $P_{z,0}\left(\delta ,\gamma \right)$ and $P_{w,0}\left(d_1,\gamma \right)$. Therefore, its bound is

$$P_0\le \frac{1}{2}$$

(56)

Using (51) and (56), (50) can be bounded as follows:

$$\begin{array}{cc}\hfill P_E& \le 2^{-M}\sum _{d_1=0,\mathbf{x}\ne \overline{\mathbf{x}}}\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U},\overline{\mathbf{x}}:{∥\overline{\mathbf{x}}∥}_0=d_1}P\left(\overline{\mathbf{x}}\right)\left(\sum _{\mathbf{v}}P\left(\mathbf{v}\right)\right)+2\epsilon \hfill \\ \hfill & \le 2^{-M}\sum _{d_1=0,\mathbf{x}\ne \overline{\mathbf{x}}}\sum _{\left(\mathbf{x},\mathbf{e}\right)\in \mathcal{U},\overline{\mathbf{x}}:{∥\overline{\mathbf{x}}∥}_0=d_1}P\left(\overline{\mathbf{x}}\right)+2\epsilon \hfill \\ \hfill & \le 2^{-M}\sum _{\mathbf{x}\in {\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N}\sum _{\mathbf{e}\in {\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M}\sum _{d_1=0,\mathbf{x}\ne \overline{\mathbf{x}}}P\left(\overline{\mathbf{x}}\right)+2\epsilon \hfill \\ \hfill & =2^{-M}\left|{\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N\right|·\left|{\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M\right|\sum _{d_1=0,\mathbf{x}\ne \overline{\mathbf{x}}}P\left(\overline{\mathbf{x}}\right)+2\epsilon \hfill \\ \hfill & \le 2^{-M}\left|{\mathcal{A}}_{\left[\mathbf{x}\right]\epsilon }^N\right|·\left|{\mathcal{A}}_{\left[\mathbf{e}\right]\epsilon }^M\right|+2\epsilon \hfill \\ \hfill & \le 2^{-M}{2}^{N\left(H\left(\delta \right)+\epsilon \right)}{2}^{M\left(H\left(\eta \right)+\epsilon \right)}+2\epsilon \hfill \\ \hfill & =2^{N\left(H\left(\delta \right)+\epsilon \right)+M\left(H\left(\eta \right)+\epsilon \right)-M}+2\epsilon \hfill \end{array}$$

(57)

As the probability of error is less than 1, the exponent term on the right side of (57) is bounded by

$$N\left(H\left(\delta \right)+\epsilon \right)+M\left(H\left(\eta \right)+\epsilon \right)-M<0$$

(58)

Then, the ratio of M to N is

$$\frac{M}{N}>\frac{H\left(\delta \right)+\epsilon }{1-H\left(\eta \right)-\epsilon }$$

(59)

This completes the proof of Theorem 3. □

5.2. Discussion for Necessary and Sufficient Conditions

In this section, we discuss the results obtained from Theorems 2 and 3. The result from Theorem 2 allows us to solve the lower bound in the NTGT problem using Fano’s inequality. The minimum number of tests required to recover all defective samples with $\delta$ probability out of N samples is also obtained. In other words, Theorem 2 is a necessary condition for any probability of error to be smaller than $\rho$. Conversely, Theorem 3 leads to the upper bound on the probability of an error using the MAP decoding method. This condition refers to the upper bound on performance and is the sufficient condition to allow us to reconstruct defective samples.

We show that the results of Theorems 2 and 3 coincide with each other. Finding and presenting the necessary and sufficient conditions for the number of tests required in the NTGT problem is significant for TGT. In addition, as shown in (27) above, a system design method for NTGT was proposed so that the probability that a test result is 0 and the probability that it is 1 are the same depending on threshold T.

6. Conclusions

In this paper, we considered a NTGT problem where the test result is positive when the number of defective samples in a pool equals or greater than a certain threshold. Recently, when performing GT for the diagnosis COVID-19 infection, if the sample’s virus concentration did not sufficiently reach the threshold, false positives or false negatives can occur, so in this work we dealt with this TGT framework. In addition, a noise model was added in case pure results were flipped due to unexpected measurement noise. We took into account how many tests were needed to successfully reconstruct a small defective sample with the NTGT problem. To this end, we aimed to find the necessary and sufficient conditions for the number of tests required. For the necessary condition, we obtained the lower bound on the number of tests using Fano’s inequality theorem. Next, the upper bound on performance defined by the probability of error was derived using the MAP decoding method. This result leads to the sufficient condition for identifying all defective samples in the NTGT problem. In this paper, we have shown that the necessary and sufficient conditions are consistent with the NTGT framework. In addition, we presented that the relationship between the defective rate of the input signal and the sparsity of the group matrix should be considered to design an optimal NTGT system.