---
abstract: 'One of the main challenges in containing the Coronoavirus disease 2019 (COVID-19) pandemic stems from the difficulty in carrying out efficient mass diagnosis over large populations. The leading method to test for COVID-19 infection utilizes qualitative polymerase chain reaction, implemented using dedicated machinery which can simultaneously process a limited amount of samples. A candidate method to increase the test throughput is to examine pooled samples comprised of a mixture of samples from different patients. In this work we study pooling-based COVID-19 tests. We identify the specific requirements of COVID-19 testing, including the need to characterize the infection level and to operate in a one-shot fashion, which limit the application of traditional group-testing (GT) methods. We then propose a multi-level GT scheme, designed specifically to meet the unique requirements of COVID-19 tests, while exploiting the strength of GT theory to enable accurate recovery using much fewer tests than patients. Our numerical results demonstrate that multi-level GT reliably and efficiently detects the infection levels, while achieving improved accuracy over previously proposed one-shot COVID-19 pooled-testing methods.'
author:
- '[^1]'
bibliography:
- 'refs.bib'
title: 'Multi-Level Group Testing with Application to One-Shot Pooled COVID-19 Tests'
---

Introduction {#sec:intro}
============

The Coronoavirus disease 2019 (COVID-19) pandemic has already forced lockdowns all over the globe, and has claimed more than a million lives worldwide. In order to handle and contain the pandemic in the absence of a vaccine, large portions of the population should be frequently tested @salathe2020covid. One of the main difficulties in doing so stems from the limited testing resources and the lengthy duration required to identify the presence of an infection @emanuel2020fair.

The main diagnosis tool for COVID-19 tests is based on RNA extraction via . Although various technological alternatives have been proposed @lucia2020ultrasensitive [@ben2020sars], the process remains the leading and most widely spread method for COVID-19 testing. The output of this procedure represents an estimate of the viral load in the tested sample @nolan2006quantification. The main bottleneck associated with this form of COVID-19 testing follows from the fact that each machine can simultaneously process a fixed number of samples, and its procedure tends to be quite lengthy, on the order of a few hours for each test.

A promising method to increase the efficiency of COVID-19 tests is based on pooling @yelin2020evaluation [@hanel2020boosting]. Here, each sample processed by the machine is comprised of a mixture of several samples taken from different patients. When the infected patients constitute a small subset of the overall tested individuals, pooling-based schemes allow accurate recovery using a number of tests which is notably smaller than the number of patients @gilbert2008group. Several recovery schemes for pooled COVID-19 tests have been recently proposed @hanel2020boosting [@ben2020large; @shental2020efficient; @ghosh2020compressed; @yi2020low; @petersen2020practical; @yi2020error; @zhu2020noisy], which can be divided according to the two main mathematical frameworks for such recovery procedures: The first is theory, originally derived for detecting infections in large populations @dorfman1943detection, which was used in @yelin2020evaluation [@hanel2020boosting; @ben2020large]; The second framework is , which deals with the recovery of sparse signals @eldar2012compressed,

and was utilized for pooled COVID-19 tests in @shental2020efficient [@ghosh2020compressed; @yi2020low; @petersen2020practical; @yi2020error; @zhu2020noisy].

The main difference between classical and is that deals with group detection problems, which results in binary variables, i.e., each subject can be either infected or not infected @gilbert2008group, while -based methods result in real-valued variables. Although group testing is traditionally adaptive, requiring multiple sequential tests based on previous ones @dorfman1943detection, it can also be applied in a one-shot (non-adaptive) manner @chan2014non. focuses on the one-shot recovery of sparse real-valued vectors from lower-dimensional linear projections, and thus each subject can take any real value number @eldar2012compressed. The additional domain knowledge of , namely, the more restricted domain over which it operates compared to , allows it in some applications to achieve improved recovery guarantees over , in terms of fewer measurements required, as suggested in @cohen2019serial [@cohen2020distributed] for the quantization of sparse signals. Nonetheless, in the context of COVID-19 testing, one is often interested not only in detecting whether or not a patient is infected, but also in some score on the level of the viral load @ghosh2020compressed, as can be provided using tools. The fact that each of these mathematical frameworks has its own pros and cons for COVID-19 testing, motivates the design of a recovery method which combines with one-shot operation and multi-level detection, as in .

In this work we propose a multi-level recovery scheme for pooled COVID-19 testing, which is a -based method designed to account for the unique characteristics of pooled COVID-19 tests. The proposed technique extends schemes to detect multiple levels of viral load, building upon our previous results on combining with concepts and multi-level discretization in @cohen2019serial. The resulting multi-level scheme operates in a one-shot manner, and is designed to avoid dilution due to mixing too many samples in each pool @yi2020optimal.

We begin by identifying the specific requirements which arise from the setup of pooled COVID-19 testing. In light of these requirements, we derive the multi-level method, which is comprised of a dedicated testing matrix, i.e., pooling pattern, as well as a -based recovery method. Our numerical evaluations, which use the model proposed in @ghosh2020compressed for pooled testing, demonstrate that the proposed multi-level scheme reliably recovers the infection levels, while operating at a limited computational burden, and achieving improved accuracy over previously proposed -based approaches.

The rest of this paper is organized as follows: In Section \[sec:Model\] we review the pooled COVID-19 testing setup. Section \[sec:MultiGT\] presents the proposed multi-level scheme. Section \[sec:sims\] details the simulation study, and Section \[sec:Conclusions\] provides concluding remarks.

Throughout the paper, we use boldface lower-case letters for vectors, e.g., ${{{\boldsymbol{x}}}}$. Matrices are denoted with boldface upper-case letters, e.g., ${{\boldsymbol{M}}}$. Sets are expressed with calligraphic letters, e.g., ${\mathcal{X}}$, and ${\mathcal{X}}^n$ is the $n$th order Cartesian power of ${\mathcal{X}}$.

System Model {#sec:Model}
============

In this section we present the system model for which we derive the recovery algorithm described in Section \[sec:MultiGT\]. As our main application is pooled COVID-19 tests, we begin by identifying the specific characteristics which arise from this application in Subsection \[subsec:Model\_Assumptions\], based on which we present our problem formulation in Subsection \[subsec:Model\_Problem\].

![Pooled testing with one-shot recovery.<span data-label="fig:LearningTech1"></span>](Flow4){width="\linewidth"}

Pooled COVID-19 Tests {#subsec:Model_Assumptions}
---------------------

The common approach in testing for the presence of COVID-19 is based on the method. Here, a sample is collected, most commonly swab-based. The presence of infection is then examined by RNA extraction via measurements, quantifying the viral load in the sample. The process is quite time consuming (on the typical order of several hours), and can simultaneously examine up to a given number of ${m}$ inputs (commonly on the order of several tens of samples). This results in a major bottleneck, particularly when the number of patients, denoted by ${n}$, is much larger than ${m}$.

A candidate approach to reduce the test duration, which is considered in this paper, utilizes pooling @yelin2020evaluation. Pooling is based on mixing the samples of groups of patients together, forming ${m}$ mixed samples out of the overall ${n}$ patients. Then, the presence of COVID-19 for each of the tested individuals is recovered from the mixed measurements, either directly, i.e., in a <span>*one-shot*</span> fashion, or in an adaptive manner, which involves additional tests @hughes1994two. To formulate the problem of designing pooling-based recovery techniques for COVID-19 tests, we note the following characteristics of this testing procedure which have to be accounted for:

1.  : \[itm:sparsity\] The number of infected measurements, denoted by ${k}$, is much smaller than the number of tested individuals ${n}$. Typically ${k}\leq 0.1 {n}$, i.e., up to $10\%$ of the tested population is infected.

2.  : \[itm:Val\] One is interested not in only identifying whether a subject is infected or not, but also in some discrete score on the viral load. For example, possible outputs are <span>*no*</span> (no virus), <span>*low*</span> (borderline), <span>*mid*</span> (infected), and <span>*high*</span> (highly infected).

3.  : \[itm:Noise\] The measurements are noisy, i.e., some level of random distortion is induced in the overall process, encapsulating the randomness in the acquisition of the samples, their mixing, and the reading.

4.  : \[itm:OneShot\] It is preferable to carry out one-shot tests, i.e., fully identify all subjects from a single operation, without having to carry out additional tests based on the results.

5.  :\[itm:Limit\] There is a limit, denoted by ${L}> 1$, on the number of subjects which can be mixed together in a single measurement. A typical limit on the number of subjects mixed together is ${L}= 32$ @yelin2020evaluation. Furthermore, the portion taken from each sample for the pooled measurements is identical, e.g., one cannot mix $30\%$ from one patient with $70\%$ from another patient into a single pool.

An illustration of the overall flow of pooled -based COVID-19 testing along with the desired one-shot recovery operation is depicted in Fig. \[fig:LearningTech1\]. On the left side of the figure, we see the true viral loads of all $n$ items. In particular, we see that the first item is infected in a medium level, the fourth item is infected in a low level, and all other items are not infected. Next, pooling is done based on a testing matrix, which is generated prior to obtaining the samples. For example, the first pooled test involves samples from the first, third, and fifth items. This results in a measurements vector, denoted by ${{\boldsymbol{z}}}$. This vector is fed to the recovery algorithm, which is able to tell in one-shot that the first item is infected in a medium level, the fourth item is infected in a low level, and all other items are not infected.

Problem Formulation {#subsec:Model_Problem}
-------------------

Based on the characteristics of pooled COVID-19 tests detailed above, we consider the following problem: Let ${{\boldsymbol{x}}} \in {\mathcal{R}}_{+}^{{n}}$ be a vector whose entries are the viral loads of the ${n}$ patients. By \[itm:sparsity\] it holds that ${{\boldsymbol{x}}}$ is ${k}$-sparse, i.e., $\|{{\boldsymbol{x}}}\|_0 \leq {k}$. The pooling operation is represented by the matrix ${{\boldsymbol{A}}} \in \{0,1\}^{{m}\times {n}}$. Let ${l}(i) \leq {L}$ denote the number of subjects mixed together in the $i$th individual pool, $i\in\{1,\ldots,m\}$. This implies that the $i$th row of ${{\boldsymbol{A}}}$, denoted ${{\boldsymbol{A}}}_i^T$, is ${l}(i)$-sparse by \[itm:Limit\]. The viral loads of the pooled samples are represented by the vector ${{\boldsymbol{z}}} \in {\mathcal{R}}_{+}^{{m}}$, whose entries are given by $$\label{eqn:PooledViral}
{{\boldsymbol{z}}}_i = {\frac{1}{{l}(i)}}{{\boldsymbol{A}}}_i^T{{\boldsymbol{x}}}, \quad i\in\{1,\ldots,m\},$$ where the factor $\frac{1}{{l}(i)}$ and the structure of ${{\boldsymbol{A}}}$ guarantee that identical portions are taken from each sample in a pool-test, as required in \[itm:Limit\]. The measurements, denoted by ${{\boldsymbol{y}}} \in {\mathcal{R}}_{+}^{{m}}$, are given by some stochastic mapping $f: {\mathcal{R}}_{+}\mapsto  {\mathcal{R}}_{+}$ of ${{\boldsymbol{z}}}$, which represents the distortion detailed in \[itm:Noise\]. We write the measurement as ${{\boldsymbol{y}}} = f({{\boldsymbol{z}}})$, where $f(\cdot)$ is carried out element-wise.

To formulate our objective, we note that by \[itm:Val\], we are interested in recovering a discrete representation of the viral load. We thus define the discretization mapping $Q:{\mathcal{R}}_{+}\mapsto {{\mathcal{Q}}}$, where ${{\mathcal{Q}}}$ is a finite set containing the possible decisions. Our goal is thus to design an algorithm which maps the measurements ${{\boldsymbol{y}}}$ into an estimate of the discretized viral loads, denoted by $\hat{{{\boldsymbol{x}}}}\in{\mathcal{Q}}^{{n}}$, for the objective of minimizing the error probability, defined as $$\label{eqn:error}
e(\hat{x}) \triangleq \frac{1}{{n}}\sum_{i=1}^{{n}} \Pr\left(Q(x_i) \neq \hat{x}_i \right).$$ The fact that $\hat{{{\boldsymbol{x}}}}$ is obtained directly from ${{\boldsymbol{y}}}$ indicates that the algorithm operates in a one-shot fashion, as required in \[itm:OneShot\].

To conclude, for the subset of infected items, of size ${k}$, from ${n}$, the goal in multi-level pooled COVID-19 tests is to design an ${m}\times {n}$ one-shot measurement matrix which guarantees that at most ${L}$ subjects are mixed in each pool-test and a recovery algorithm, such that by observing ${{\boldsymbol{z}}}$ we can identify the subset of infected items and their discrete representation of the viral load.

Multi-Level Group Testing {#sec:MultiGT}
=========================

In this section, we provide an efficient scheme which implements with multiple decisions. The sparsity assumption \[itm:sparsity\] implies that the recovery of pooled tests can be treated as a sparse recovery problem, as was also noted in previous works on pooled COVID-19 testing @hanel2020boosting [@shental2020efficient; @ben2020large; @ghosh2020compressed; @yi2020low; @petersen2020practical; @yi2020error; @zhu2020noisy]. Sparse recovery is typically studied under either the framework of @gilbert2008group, or that of @eldar2012compressed. Broadly speaking, deals with sparse recovery of binary variables, i.e., it can recover whether a subject is infected or not. In order to evaluate the actual levels of each tested subject, as requested in \[itm:Val\], one would have to re-run the test, violating requirement \[itm:OneShot\]. The alternative approach of operates over the domain of real numbers, namely, it attempts to identify the exact cycle threshold or viral load for each subject, and thus tends to be less accurate compared to , as it does not exploit the fact that one is only interested in a discrete grade value by \[itm:Val\]. This motivates the derivation of a dedicated algorithm for pooled COVID-19 recovery, which harnesses the strength of theory while extending it to the multi-level domain. The proposed multi-level method designed in light of the model assumptions detailed in the previous section, is presented in Subsection \[subsec:proposed\], followed by a discussion in Subsection \[subsec:Discussion\].

Pooled-Testing Algorithm {#subsec:proposed}
------------------------

Multi-level is comprised of three components: The design of the testing matrix ${{\boldsymbol{A}}}$; the pooling operation; and the recovery algorithm which determines the discrete level associated with each subject based on the results of the pooled tests. We next elaborate on each of these components.

### Testing Matrix {#subsec:testing_matrix}

To determine the testing matrix ${{\boldsymbol{A}}}$, we first set the number of the pool-tests ${m}$ to be $(1+\epsilon){k}\log_2{n}$, for some $\epsilon>0$. This is the sufficient number of pool-test for reliable recovery in using the optimal decoder @atia2012boolean [@cohen2016secure].

Once ${m}$ is fixed, we proceed to setting ${{\boldsymbol{A}}}$. The traditional method of generating ${{\boldsymbol{A}}}$ is to draw its elements in an i.i.d. fashion according to a Bernoulli distribution with parameter $p$. A Common choice for $p$ in theory is $p=1-2^{-1/k}$, for which the probability of each element in ${{\boldsymbol{z}}}$ to be zero is $1/2$. This choice of $p$ is obviously impractical, as $k$ is unknown, so $p$ is chosen using a rough approximation of $k$. A major drawback of this approach is that \[itm:Limit\] is not necessarily satisfied. We therefore consider an alternative method of generating ${{\boldsymbol{A}}}$, which forces the columns of ${{\boldsymbol{A}}}$, as well as the rows of ${{\boldsymbol{A}}}$, to be "typical". That is, we want every column/row to have exactly $\lceil p\cdot m \rceil \leq {L}$ and $\lceil p\cdot n\rceil$ ones, respectively. Since in practical COVID-19 testing setups, one is interested in using a fixed deterministic matrix, rather than having to work with random matrices, we generate ${{\boldsymbol{A}}}$ once before the pooling starts. That is, the same testing matrix can be used for multiple pooling experiments.

### Pooling {#subsec:pooling}

After the testing matrix ${{\boldsymbol{A}}}$ is generated, it determines which samples are pooled together. The pooling process is done as detailed in Section \[sec:Model\].

### Recovery Algorithm {#subsec:recovery_algorithm}

The proposed recovery algorithm is given in Algorithm \[alg:recovery\]. It operates in two main steps as detailed next.

At the first step, the algorithm identifies efficiently all of the definitely defective (DD) items in two stages, without determining the infection level. In the first stage of the first step, the algorithm @aldridge2014group is used (lines \[line:DND\] and \[line:DND\_start\]-\[line:DND\_end\]). Recall that the number of pool-tests ${m}$, corresponding to the testing matrix ${{\boldsymbol{A}}}$, is fixed to allow detection. The algorithm attempts to match the columns of ${{\boldsymbol{A}}}$ with the vector ${{\boldsymbol{y}}}$. In particular, if column $j$ of ${{\boldsymbol{A}}}$ has a non-zero entry while the correpodponding element in ${{\boldsymbol{y}}}$ is zero, the column is assumed not to correspond to a defective subject. This algorithm finds most of the subjects that are and drastically reduces the number of possible defective (PD) items. In practice, as demonstrated empirically in Fig. \[fig:typical\_dnd\_false\_negative\], in the non-asymptomatic regime as we consider herein for COVID-19, the set of subjects declared as PD after this stage, denoted ${{\cal P}}$, approximately satisfies $|{{\cal P}}|= {\mathcal{O}(k)}$. The remaining $n-|{{\cal P}}|$ subjects are declared not defective. In the second stage of the first step, the algorithm @atia2012boolean is used only over the smaller set of PD subjects ${{\cal P}}$, to identify exactly the set ${{\cal D}}$ of ${k}$ DD subjects (lines \[line:ML\] and \[line:ML\_start\]-\[line:ML\_end\]). The algorithm looks for a collection of ${k}$ columns in ${{\boldsymbol{A}}}$, for which ${{\boldsymbol{y}}}$ is most likely. In the formulation $Q(\cdot)_{0,1}$ is a binary quantization mapping, and in the rule we denote by ${{\cal K}}$ the set of actual defective subjects, and by $\Omega({{\cal P}},k)$ the set of $\binom{|{{\cal P}}|}{k}$ combinations of $k$ defective subjects in ${{\cal P}}$.

In the second step, the algorithm estimates the infection level of each subject in the set of identified defective subjects ${{\cal D}}$, in an iterative fashion (lines \[line:infection\_detection\_start\]-\[line:infection\_detection\_end\]). Let ${{\cal D}}(i)$ be the $i$-th element of ${{\cal D}}$, and ${{\boldsymbol{A}}}_{{{\cal D}}}$ denote the matrix created by taking the columns of ${{\cal D}}$ from ${{\boldsymbol{A}}}$. For a test in which only one infected subject participates according to the testing matrix (lines \[line:sum\_one\]-\[line:find\_one\]), the algorithm can recover the viral load directly from the measurement (lines \[line:quantize\]-\[line:save\]). To obtain a discrete score, the measured value is quantized using a threshold-based quantization mapping $Q(\cdot)$. Then the algorithm subtracts the viral load of that subject from all the tests in which it participates (line \[line:subtract\_viral\_load\]), and repeats until it recovers the infection levels of all declared infected subjects, denoted by ${{\cal S}}$ (line \[line:while\_not\_done\]).

Input: ${{\boldsymbol{A}}}, {{\boldsymbol{y}}}$Output: ${{\cal S}}$

\[1\] ${{\cal S}}\gets\emptyset$ **: Detection of defective subjects** ${{\cal P}}\gets\text{DND}(Q_{0,1}({{\boldsymbol{y}}}),{{\boldsymbol{A}}})$ \[line:DND\] ${{\cal D}}\gets\text{ML}(Q_{0,1}({{\boldsymbol{y}}}),{{\boldsymbol{A}}},{{\cal P}})$ \[line:ML\] **: Iterative viral load detection** ${{\boldsymbol{\hat{A}}}}\gets {{\boldsymbol{A_{{{\cal D}}}}}}$\[line:infection\_detection\_start\] $\bar{{{\boldsymbol{y}}}}\gets\sum_{i\in{{\cal D}}}{{\boldsymbol{A}}}_i$ \[line:while\_S\_k\]\[line:while\_not\_done\] \[line:sum\_one\] $j\gets$ index s.t. ${{\boldsymbol{\hat{A}}}}_{i,j}=1$\[line:find\_one\] $\hat{{{\boldsymbol{x}}}}_i\gets Q({{\boldsymbol{y}}}_i)$\[line:quantize\] ${{\cal S}}= {{\cal S}}\cup \left\{ ({{\cal D}}(j), {{\boldsymbol{\hat{x}}}}_i) \right\}$\[line:save\] $\bar{{{\boldsymbol{y}}}}\gets \bar{{{\boldsymbol{y}}}} - {{\boldsymbol{A}}}_j$\[line:subtract\_viral\_load\] \[line:infection\_detection\_end\]

Definitely Not Defective () @chan2014non for $m =(1+\epsilon) {k}\log_2 {n}$

\[line:DND\_start\] ${{\cal P}}\gets\left\{1,\ldots,n \right\}$ ${{\cal P}}\gets{{\cal P}}\setminus\left\{ j\right\}$ ${{\cal P}}$ \[line:DND\_end\]

Maximum Likelihood () @atia2012boolean only for ${{\cal P}}$ (not for ${n}$)

\[line:ML\_start\] $\arg\max_{{{\cal D}}\in\Omega({{\cal P}},k)} P(Q_{0,1}({{\boldsymbol{y}}})\mid {{\boldsymbol{A}}}, {{\cal K}}={{\cal D}})$\[line:omega\] \[line:ML\_end\]

\[b\]<span>.32</span> ![image](result_typical_code_k5_n105_3){width="\linewidth" height="1in"}

\[b\]<span>.32</span> ![image](typical_dnd_false_negative_k5_n105_1){width="\linewidth" height="1in"}

\[b\]<span>.32</span> ![image](typical_dnd_prob_k5_n105_2){width="\linewidth" height="1in"}

\[fig:Conf\]

\[b\]<span>.3</span> ![image](Conf_N105_T45){width="\linewidth" height="1.3in"}

$\quad$

\[b\]<span>.3</span> ![image](Conf_N961_T70){width="\linewidth" height="1.3in"}

$\quad$

\[b\]<span>.3</span> ![image](Conf_N961_T93){width="\linewidth" height="1.3in"}

\[fig:Conf\]

Discussion {#subsec:Discussion}
----------

The novelty of our algorithm stems from the efficiency in the first step with few pool-tests, and the iterative process in the second step, which determines the discrete infection level of each item. Here, we note a few remarks arising from the proposed multi-level scheme.

In Subsection \[subsec:proposed\] we describe how the testing matrix ${{\boldsymbol{A}}}$ is generated. The description involves a random generation procedure, for which the resulting matrix is not guaranteed to satisfy \[itm:Limit\]. The motivation for using such random procedures as in theory stems from their provable performance guarantees @gilbert2008group. Once a typical testing matrix satisfying \[itm:Limit\] is selected, one does not have to generate a new matrix for each group of ${n}$ patients.

According to theory, for ${n}$ i.i.d. tested individuals, the algorithm which maximizes the probability of finding the infected items (though not necessarily their levels) is the algorithm. However, its complexity is burdensome, as it has to consider $\binom{n}{k}$ options @coja2020information [@aldridge2019group]. An efficient alternative is the algorithm, also known as column matching @kautz1964nonrandom [@chan2014non; @aldridge2014group], whose time complexity is ${\mathcal{O}(kn\log n)}$ @cohen2016secure. However, it requires a greater amount of pooled measurements compared to the algorithm in order to reliably identify the detective items. Our proposed multi-level method combines the concepts of with the algorithm, while extending them to operate over non-binary fields, i.e., recover multiple levels rather than just identifying which subject is defective. Performing on all ${n}$ items using the number of tests set to allow detection, i.e., ${m}= (1+\epsilon) {k}\log_2 {n}$, results in a smaller set of PD subjects ${{\cal P}}$. Given ${{\cal P}}$, the decoder has to consider significantly less options, $\binom{|{{\cal P}}|}{k}$, which is likely to be computationally feasible and considerably faster than considering all $\binom{n}{k}$ combinations.

In the second step of the algorithm proposed, we analyze the tests in which only one infected subject participates according to ${{\boldsymbol{A}}}$. This process, when restricted to operate over binary variables, was proposed as means to identify the DD subjects in @aldridge2014group. Unlike @aldridge2014group, we utilize this process in iterative fashion after the DD subjects are already detected to determine the viral load infection over the non-binary field. By subtracting the viral load of each detected subject in the iterative algorithm, we reduce the number of pool-tests in @aldridge2014group to the one required in the algorithm. In the case where it is possible to identify the number of infected subjects in a pool-test, by observing its measurement, we noticed empirically that it is possible to achieve the lower bound number of pool test suggested for using algorithm, i.e., $m \approx \log_2 \binom{{n}}{{k}} \leq {k}\log_2 ({n}/{k}) $ @atia2012boolean [@chan2014non]. We leave this interesting case and the analytical and complexity analysis of the proposed iterative algorithm as future work.

Numerical Evaluations {#sec:sims}
=====================

We assessed the performance of our method using the -based COVID-19 test model of @ghosh2020compressed. The elements of the test matrix are chosen such that the rows and columns of ${{\boldsymbol{A}}}$ are typical. The number of items selected in the first example is $n=105$, out of which $k=5$ items are defective, and with $4$ infection levels. The viral load of each defective item is drawn from a uniform distribution between $\left[0,1000\right]$ as in @ghosh2020compressed. The infection level score is based on the following division of this interval into $4$ regions: $[0,50)$ = no; $[50,300)$ = low (borderline); $[300,700)$ = mid; and $>700$ = high. The success probability of Algorithm \[alg:recovery\] versus ${m}$ is depicted in Fig. \[fig:result\_typical\_matrix\], compared to the lower/upper bound on the number of tests ${m}$ from theory, as described in @atia2012boolean. We evaluate forms of the success probability measure: here an error is declared when there is at least a single defective subject who is not detected out of a set of ${n}$ patients, as well as when there is at least one patient whose infection level is not correctly recovered. From the plot, we see that the success probability of finding the defective items and the success probability of finding the infection levels coincide. That is, whenever the defective set was recovered successfully, the correct infection levels were also estimated successfully, indicating the validity of step 2 of Algorithm \[alg:recovery\]. We also see that when the number of tests is at the ML upper bound, the probability of success approaches one.

Fig. \[fig:typical\_dnd\_false\_negative\] shows the number of true positives, i.e. the number of defective subjects that are declared defective. We can see that when the number of tests ${m}$ matches the upper bound, we have no false negatives with high probability. In the context of COVID-19, false negatives are considered to be the worst outcomes of a test. Fig. \[fig:result\_typical\_probability\] illustrates the probability of the detected non-defective subjects after the stage in Algorithm \[alg:recovery\]. This is calculated as the number of non-defective items declared by the algorithm, divided by the total number of non-defective items. We see that when the number of tests is as the upper bound of dictates, the algorithm identifies $\approx \frac{95}{100} = 95\%$ of the subjects as non-defective, i.e., $|{{\cal P}}| \approx 2k$. These will be candidates to be tested in the second stage of algorithm as PD, demonstrating the notable complexity reduction achieved by the two-step process.

The results in Figs. \[fig:result\_typical\_matrix\]-\[fig:result\_typical\_probability\] evaluate the error probability, but do not capture which forms of errors are produced when using Algorithm \[alg:recovery\]. Therefore, we depict in Fig. \[fig:Conf\] the confusion matrix for the considered scenario, as well as when repeating the setup with a much larger amount of patients of ${n}= 961$, using merely ${m}\in \{70, 93\}$ pool-tests. The values $({n}, {m}) \in \{(105,45), (961,93)\}$ were also used in @ghosh2020compressed, which applied tools for recovery. Observing Fig. \[fig:Conf\], we note that most of the errors reported in fact correspond to identifying low-level and mid-level subjects as mid and high, respectively. Such errors are much less harmful in COVID-19 tests compared to reporting non-infected subjects as defective, which occurs only $\approx 0.1\%$ of the times for $({n}, {m}) = (105,45)$ in Fig. \[fig:Conf1\], which is similar to the results achieved in @ghosh2020compressed for such setups. This behavior is more notable when jointly testing ${n}=961$ subjects in Figs. \[fig:Conf2\]-\[fig:Conf3\]. Comparing these results to @ghosh2020compressed, it is noted that multi-level achieves improved false positive and false negative probabilities with only ${m}=70$ test-pools compared to that achieved using all methods examined in @ghosh2020compressed with ${m}=93$ test-pools. For instance, for $({n}, {m}) = (961,93)$ @ghosh2020compressed reported false positive probabilities varying from $0.1\%$ to $0.8\%$, while the corresponding probability in Fig. \[fig:Conf2\] is $0.0\%$. This indicates the potential of multi-level in facilitating pooled testing of large numbers of subjects.

Conclusions {#sec:Conclusions}
===========

In this work we proposed a scheme coined multi-level for one-shot pooled COVID-19 tests. We first identified the unique characteristics and requirements of -based COVID-19 tests. Based on these requirements, we designed multi-level to combine traditional methods with one-shot operation and multi-level outputs, while implementing a preliminary detection mechanism to facilitate recovery at reduced complexity. Our numerical evaluations demonstrate that multi-level reliably identifies the infection levels when examining a much smaller number of samples compared to the number of tested subjects.

[^1]: This project received funding from the Benoziyo Endowment Fund for the Advancement of Science, the Estate of Olga Klein - Astrachan, the European Union's Horizon 2020 research and innovation program under grant No. 646804-ERC-COG-BNYQ, and from the Israel Science Foundation under grant No. 0100101. A. Cohen, A. Solomon and M. Médard are with the Research Laboratory of Electronics, MIT, Cambridge, MA (email: {cohenale, amitsol, mirandagraham@example.net). N. Shlezinger is with the School of ECE, Ben-Gurion University of the Negev, Be'er-Sheva, Israel (e-mail: mirandagraham@example.net). Y. C. Eldar is with the Faculty of Math and CS, Weizmann Institute of Science, Rehovot, Israel (e-mail: mirandagraham@example.net).

{'source': 'arXiv_out/2010'}