# Assessing the safety benefits of CACC+ based coordination of connected and
autonomous vehicle platoons in emergency braking scenarios

Guoqi Ma, Prabhakar R. Pagilla∗, Swaroop Darbha The authors are with the
Department of Mechanical Engineering, Texas A&M University, College Station,
TX 77843, USA. E-mails: {gqma, ppagilla<EMAIL_ADDRESS>∗Corresponding
author.

###### Abstract

Ensuring safety is the most important factor in connected and autonomous
vehicles, especially in emergency braking situations. As such, assessing the
safety benefits of one information topology over other is a necessary step
towards evaluating and ensuring safety. In this paper, we compare the safety
benefits of a cooperative adaptive cruise control which utilizes information
from one predecessor vehicle (CACC) with the one that utilizes information
from multiple predecessors (CACC+) for the maintenance of spacing under an
emergency braking scenario. A constant time headway policy is employed for
maintenance of spacing (that includes a desired standstill spacing distance
and a velocity dependent spacing distance) between the vehicles in the
platoon. The considered emergency braking scenario consists of braking of the
leader vehicle of the platoon at its maximum deceleration and that of the
following vehicles to maintain the spacing as per CACC or CACC+. By focusing
on the standstill spacing distance and utilizing Monte Carlo simulations, we
assess the safety benefits of CACC+ over CACC by utilizing the following
safety metrics: (1) probability of collision, (2) expected number of
collisions, and (3) severity of collision (defined as the relative velocity of
the two vehicles at impact). We present and provide discussion of these
results.

##  I INTRODUCTION

Connected and autonomous vehicles (CAVs) have been receiving extensive
attention in recent decades due to the substantial benefits they could offer
in terms of increasing traffic capacity, improving fuel economy and reducing
transportation costs [1, 2, 3]. Utilization of advanced communication
technologies, such as Dedicated Short Range Communications (DSRC) [4],
Vehicle-to-Vehicle (V2V) communication [5], or more inclusive Vehicle-to-
Everything (V2X) communication [6], can be a strong enabler for CAVs to
achieve such benefits. Most existing studies have focused on string stability
of the platoon in the presence of external disturbances, i.e., the effect of
information topology on the inter-vehicular spacing error propagation along
the vehicle stream, see e.g. [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17] and
references therein. While string stability can ensure collision avoidance,
however, such performance is usually achieved without considering of the
capabilities of each vehicle in the platoon, i.e., actuator saturation or
acceleration/deceleration limitations of the vehicles.

A significant safety situation could occur due to an emergency braking
scenario, where the lead vehicle may have to brake with its maximum
deceleration to avoid a crash. Ideally, if all the following vehicles can
brake with the same deceleration as the lead vehicle and react
instantaneously, then there would be no collisions. However, in practice, the
maximum deceleration capacity of each vehicle is not identical for many
reasons (wear, type of vehicle, road conditions, etc.,) [18]. Although the
following vehicles could brake with their own maximum deceleration, this could
cause exacerbated collision occurrence when the maximum deceleration is non-
identical for the vehicles in the platoon. Due to the complexity of the
factors that influence safety, such as uncertain/stochastic actuator
saturation, initial velocity, standstill spacing, control gain values, it is
difficult to analytically derive the safety metrics for quantitative
evaluations related to these factors. Therefore, a realistic, yet beneficial,
way to assess the safety metrics is by using numerical methods. Further, it is
also infeasible to utilize a brute force approach to numerically consider and
evaluate the safety metrics for all the possible combinations in the search
space. As a result, a practical and tractable way is to estimate the safety
metrics through empirical simulation algorithms, such as the Monte Carlo
simulation approach, by considering some key aspects such as standstill
spacing, time headway and the number of predecessor vehicles. Such numerical
strategies have been employed to draw meaningful conclusions on safety in the
previous work [19, 20, 21, 22, 23].

However, existing work focused on the CACC case where only information from
the immediate predecessor was utilized. Motivated by the work in [1] which
highlighted the benefits of V2V communication on improving platoon tightness
and mobility, in this paper we highlight the safety benefits of CACC+ based
CAVs where multiple-predecessor vehicles’ information is communicated on
improving the aforementioned safety metrics in emergency braking scenarios. By
assuming the vehicles have an independent and identically distributed (i.i.d.)
maximum deceleration, we will consider the case that the lead vehicle brakes
with its maximum deceleration while the following vehicles brake according to
the designed coordination control law subject to a stochastically distributed
maximum deceleration. We will evaluate the safety metrics under all the
possible maximum deceleration values of the lead vehicle. In addition, we will
choose one of the influencing factors on safety metrics, the standstill
spacing, to evaluate the effectiveness of CACC+ under a smaller standstill
spacing in ameliorating the safety metrics by comparing with CACC under a
larger standstill spacing. The main contributions of the paper lie in problem
setup and formulation, including the modeling of the emergency scenario and
simulation framework, which can be utilized by the ITS community to evaluate
safety metrics on various CAVs with various information topologies.

The remainder of the paper is organized as follows. Section II contains
preliminaries including the vehicle dynamics and control law associated with
CACC and CACC+ with the constant time headway policy. The simulation algorithm
is developed in Section III. An illustrative numerical example and simulation
results are provided in Section IV. Finally, some concluding remarks are given
in Section V.

##  II PRELIMINARIES

###  II-A Vehicle String Model

Consider a string of homogeneous vehicles equipped with V2V communication as
illustrated in Fig. 1.

Figure 1: An illustration of the connected and autonomous vehicle platoon with
V2V communication.

The dynamics model of the $i$-th vehicle in the string is given by

$\displaystyle\left\\{\begin{array}[]{*{20}{l}}\dot{x}_{i}(t)=v_{i}(t),\\\
\dot{v}_{i}(t)=a_{i}(t),\\\
\tau\dot{a}_{i}(t)+a_{i}(t)=u_{i}(t),\end{array}\right.$ (4)

where $x_{i}(t)$, $v_{i}(t)$, $a_{i}(t)$, $u_{i}(t)$ represent the position,
velocity, acceleration, and control input of the $i$-th vehicle at time
instant $t$, and $i\in\mathcal{N}=\\{1,2,\cdots,N\\}$, where $N$ is the total
number of the following vehicles in the platoon, $\tau$ denotes the parasitic
actuation lag. It is assumed that $\tau$ is uncertain with
$\tau\in\left(0,\tau_{0}\right]$, where $\tau_{0}$ is a positive real
constant.

We first define the generalized or velocity-dependent inter-vehicular spacing
error for the $i$-th vehicle as follows:

$\displaystyle\delta_{i}(t)=e_{i}(t)+h_{w}v_{i}(t),$ (5)

where $e_{i}(t)=x_{i}(t)-x_{i-1}(t)+d$ is the spacing error for the $i$-th
vehicle, where $d$ is the minimum or standstill spacing between adjacent
vehicles, $h_{w}$ is the time headway.

###  II-B Coordination Control Law Design

Consider the following decentralized coordination control law for the $i$-th
vehicle:

$\displaystyle u_{i}(t)$
$\displaystyle=\sum\limits_{q=1}^{r}\Big{(}k_{a}a_{i-q}(t)-k_{v}(v_{i}(t)-v_{i-q}(t))$
$\displaystyle~{}~{}-k_{p}(x_{i}(t)-x_{i-q}(t)+dq+qh_{w}v_{i}(t))\Big{)},$ (6)

where $k_{a}$, $k_{v}$, $k_{p}$ are positive controller gains to be designed,
$r$ denotes the number of “look-ahead” predecessors for vehicle $i$. Then the
inter-vehicular spacing error propagation equation is given by

$\displaystyle\delta_{i}(s)=H(s)\sum\limits_{q=1}^{r}\delta_{i-q}(s),$ (7)

where $H(s)=N_{H}(s)/D_{H}(s)$ with $N_{H}(s)=k_{a}s^{2}+k_{v}s+k_{p}$,
$D_{H}(s)=\tau s^{3}+s^{2}+\gamma s+rk_{p}$ with
$\gamma=rk_{v}+rk_{p}\frac{r+1}{2}h_{w}$. As discussed in [1], a sufficient
condition to ensure robust string stability (robustness with respect to the
parasitic actuation lag, $\tau\in(0,\tau_{0}]$) of the vehicle platoon is
given by

$\displaystyle\|rH(s)\|_{\infty}\leq 1.$ (8)

Let $\tilde{H}(s)=rH(s)$, and define $\tilde{k}_{a}=rk_{a}$,
$\tilde{k}_{v}=rk_{v}$, $\tilde{k}_{p}=rk_{p}$,
$\tilde{h}_{w}=\frac{r+1}{2}h_{w}$, then from
$\|\tilde{H}(j\omega)\|_{\infty}\leq 1$, we can obtain $\tilde{k}_{a}\in(0,1)$
and the admissible region of $\tilde{k}_{v}$ and $\tilde{k}_{p}$ as

$\displaystyle\begin{cases}{}\frac{\tilde{k}_{v}}{a_{1}}+\frac{\tilde{k}_{p}}{b_{1}}\leq
1,\\\ \frac{\tilde{k}_{v}}{a_{2}}+\frac{\tilde{k}_{p}}{b_{2}}\geq
1,\end{cases}$ (9)

where

$\displaystyle
a_{1}=\frac{1-\tilde{k}_{a}^{2}}{2\tau_{0}},b_{1}=\frac{1-\tilde{k}_{a}^{2}}{2\tau_{0}\tilde{h}_{w}},a_{2}=\frac{1-\tilde{k}_{a}}{\tilde{h}_{w}},b_{2}=\frac{2(1-\tilde{k}_{a})}{\tilde{h}_{w}^{2}}.$

In order to ensure (9) has positive solutions for $\tilde{k}_{v}$ and
$\tilde{k}_{p}$, we need $a_{1}>a_{2}$, i.e.,

$\displaystyle\frac{1-\tilde{k}_{a}^{2}}{2\tau_{0}}>\frac{1-\tilde{k}_{a}}{\tilde{h}_{w}},$
(10)

from which we can obtain $\tilde{h}_{w}>\frac{2\tau_{0}}{1+\tilde{k}_{a}}$,
that is, $h_{w}$ satisfies:

$\displaystyle\tilde{h}_{w}>\frac{4\tau_{0}}{(1+r)(1+r{k}_{a})}.$ (11)

Note that the control law (II-B) does not take into account actuator
saturation, or vehicle acceleration/deceleration capability. When this
constraint is incorporated, the actual input to the $i$-th vehicle, denoted as
$\bar{u}_{i}$, is given by

$\displaystyle\bar{u}_{i}=sat(u_{i})=\begin{cases}{}-D_{i},\
\mbox{when}~{}u_{i}<-D_{i},\\\ u_{i},\ \ \ \ \ \mbox{when}~{}-D_{i}\leq
u_{i}\leq D_{i},\\\ D_{i},\ \ \ \ \mbox{when}~{}u_{i}>D_{i}.\end{cases}$ (12)

An illustration of the saturation function $sat(u_{i})$ is shown in Fig. 2.

Figure 2: An illustration of the saturation function $sat(u_{i})$.

In practice, it is reasonable to assume the vehicle maximum
acceleration/deceleration, $D_{i}$, varies in a bounded interval such that
$D_{i}\in[D_{\rm lower},D_{\rm upper}]$. Besides, to facilitate numerical
evaluations in this range of $D_{i}$, we model the interval $[D_{\rm
lower},D_{\rm upper}]$ as arithmetic progression with a certain probability
distribution, i.e.,

$\displaystyle\begin{cases}{}D_{i}\in\\{\hat{D}_{1},\hat{D}_{2},\cdots,\hat{D}_{m}\\},\\\
\mathbb{P}\\{D_{i}=\hat{D}_{j}\\}=p_{j},j=1,\cdots,m,\\\
\sum\limits_{j=1}^{m}p_{j}=1,\end{cases}$ (13)

where $\hat{D}_{1}=D_{\rm lower}$, $\hat{D}_{m}=D_{\rm upper}$,
$\mathbb{P}\\{D_{i}=\hat{D}_{j}\\}$ denotes the probability of $D_{i}$ taking
the value of $\hat{D}_{j}$, and $m$ is the discretization number of the
interval $[D_{\rm lower},D_{\rm upper}]$.

##  III Setup and Approach for Assessing Safety

###  III-A Discretization of the Continuous-Time Dynamics Model

To discrete the continuous-time vehicle dynamics for implementation in
computer simulation, we consider $h$ to be the discretization time step size,
$k$ be the discretization index, and $x_{i}[k],v_{i}[k],a_{i}[k]$ denote the
discretized position, velocity, and acceleration of the $i$-th vehicle at time
step $k$. Let the initial conditions for the $i$-th vehicle be:
$x_{i}[0]=\bar{x}_{i}=-id-ih_{w}v_{i}[0]$, $v_{i}[0]=\bar{v}_{i}$,
$a_{i}[0]=0$, where $\bar{v}_{i}$ is the steady-state velocity. By utilizing
the fourth-order Runge-Kutta approach, the continuous-time dynamics for the
$i$-th vehicle as given by (4) can be discretized as follows:

$\displaystyle\begin{cases}{}x_{i}[k+1]=x_{i}[k]+v_{i}[k]h,\\\
v_{i}[k+1]=v_{i}[k]+a_{i}[k]h,\\\
a_{i}[k+1]=a_{i}[k]+\frac{h}{6}(k_{1}+2k_{2}+2k_{3}+k_{4}),\end{cases}$ (14)

where

$\displaystyle\begin{cases}{}k_{1}=-\frac{1}{\tau}a_{i}[k]+\frac{1}{\tau}u_{i}[k],\\\
k_{2}=-\frac{1}{\tau}(a_{i}[k]+\frac{h}{2}k_{1})+\frac{1}{\tau}u_{i}[k],\\\
k_{3}=-\frac{1}{\tau}(a_{i}[k]+\frac{h}{2}k_{2})+\frac{1}{\tau}u_{i}[k],\\\
k_{4}=-\frac{1}{\tau}(a_{i}[k]+hk_{3})+\frac{1}{\tau}u_{i}[k],\end{cases}$
(15)

and $u_{i}[k]$ is the discretized version of (II-B), which is given by

$\displaystyle u_{i}[k]$
$\displaystyle=\sum\limits_{q=1}^{r}\Big{(}k_{a}a_{i-q}[k]-k_{v}(v_{i}[k]-v_{i-q}[k])$
$\displaystyle~{}~{}-k_{p}(x_{i}[k]-x_{i-q}[k]+dq+qh_{w}v_{i}[k])\Big{)}.$
(16)

For the first $(r-1)$ following vehicles that have less than $r$ predecessor
vehicles for communication, e.g., vehicle 1 and vehicle 2 when $r=3$, the
control law is given by

$\displaystyle u_{i}[k]$
$\displaystyle=\sum\limits_{q=1}^{i}\Big{(}k_{a}a_{i-q}[k]-k_{v}(v_{i}[k]-v_{i-q}[k])$
$\displaystyle~{}~{}-k_{p}(x_{i}[k]-x_{i-q}[k]+dq+qh_{w}v_{i}[k]\Big{)}.$ (17)

Taking actuator saturation into account, the actual control input to the
$i$-th vehicle at time step $k$ is given by

$\displaystyle\bar{u}_{i}[k]=sat(u_{i}[k]),$ (18)

where the saturation function $sat(.)$ is defined in (12).

###  III-B Monte Carlo Simulation Approach

Monte Carlo simulation is an effective way to estimate the expected value of a
random variable. According to [24], the accuracy of the estimation is
quantified by

$\displaystyle Prob\\{|X_{n}-X_{t}|>\varepsilon\\}\leq
2e^{-2n\varepsilon^{2}},$ (19)

where $X_{n}$ and $X_{t}$ represent the mean estimated value after $n$
iterations and the true expected value for a random variable $X$,
respectively. Then, we have

$\displaystyle\lim\limits_{n\rightarrow\infty}Prob\\{|X_{n}-X_{t}|>0\\}=0,$
(20)

i.e. $\lim\limits_{n\rightarrow\infty}X_{n}=X_{t}$. Thus, for a sufficiently
large $n$, the estimated expected value can tend to the true expected value of
the random variable. As such, in the following, we will adopt the Monte Carlo
simulation approach to estimate the expected values of the safety metrics.

###  III-C Collision Model and Safety Metrics

####  III-C1 Collision Model

For each iteration, at time step $k$, if

$\displaystyle x_{i}[k]\geq x_{i-1}[k],$ (21)

then a collision occurs between vehicle $i$ and vehicle $i-1$ at time step
$k$. If a collision occurs between vehicle $i$ and vehicle $i+1$, without
considering the coefficient of restitution [20], we assume that vehicle $i$
and vehicle $i-1$ will stop immediately and will not move any more, i.e.,

$\displaystyle\begin{cases}{}a_{i}[l]=a_{i-1}[l]=0,\\\
v_{i}[l]=v_{i-1}[l]=0,\\\ x_{i}[l]=x_{i}[k],x_{i-1}[l]=x_{i-1}[k],\end{cases}$
(22)

$l=k+1,k+2,\cdots,K$, where $K$ is the total number of simulation steps.

####  III-C2 Safety Metrics

We will consider the following safety metrics: (1) the probability of
collision; (2) the expected number of collisions; and (3) the severity of
collisions (defined as the relative velocity of collisions at impact).

First, the probability of collision $\mathbb{P}$ is defined as

$\displaystyle\mathbb{P}=\frac{\mathcal{C}}{n}\times 100\%,$ (23)

where $\mathcal{C}=\sum\limits_{j=1}^{n}C(j)$, $n$ is the total iterations (or
samples), and the binary number $C(j)$ indicates whether there is a collision
in the $j$-th iteration and is given by

$\displaystyle\begin{cases}{}C(j)=0,\mbox{if there is no collision in the
$j$-th iteration};\\\ C(j)=1,\mbox{if there is a collision in the $j$-th
iteration}.\end{cases}$ (24)

Second, the expected number of collisions $\mathbb{N}$ is defined as

$\displaystyle\mathbb{N}=\frac{\mathcal{N}}{n},$ (25)

where $\mathcal{N}=\sum\limits_{j=1}^{n}N(j)$, where $N(j)$ denotes the number
of collisions in the $j$-th iteration.

Third, the severity of collision is defined as

$\displaystyle\mathbb{S}=\frac{\mathcal{V}}{n},$ (26)

where $\mathcal{V}=\sum\limits_{j=1}^{n}V(j)$ and $V(j)$ denoting the sum of
the relative velocity of collisions in the $j$-th iteration.

Based on the above definitions of the collision model and safety metrics, the
simulation procedure employed is provided in Algorithm 1.

Algorithm 1 Monte Carlo Safety Metric Evaluation Algorithm for Connected and
Autonomous Vehicle Platoons with i.i.d. Maximum Deceleration in Emergency
Braking Scenarios

1: Initialization: Given platoon length $N$, initial values for vehicles
$a_{l}[0]=0$, $v_{l}[0]=\bar{v}_{l}$, $x_{l}[0]=\bar{x}_{l}$, $l=1,\cdots,N$,
the number of predecessors providing information $r$, the control gains
$k_{a}$, $k_{v}$, $k_{p}$, $h_{w}$ satisfying robust string stability
condition, set maximum number of iteration steps $n$, discretization time step
$h$, simulation time $\mathscr{T}$, and the number of simulation steps
$K=\mathscr{T}/h$; and set collision number $CN=0$. Given the i.i.d. maximum
deceleration set $\mathscr{D}$, generate a probability matrix
$\mathcal{P}_{n\times N}={\rm unifrnd}(0,1,[n,N])$, and the maximum
deceleration matrix $\mathcal{D}_{n\times N}$ according to $\mathscr{D}$ and
$\mathcal{P}_{n\times N}$.

2: for each $i\in[1,n]$ do

3: Let $CS_{l}=0$, $RV_{l}=0$, $D_{l}=\mathcal{D}(i,l)$, $l=1,\cdots,N$; %
$CS_{l}$ denotes the collision status of the $l$-th vehicle, $RV_{l}$ denotes
the relative velocity at impact for the $l$-th vehicle with its predecessor
vehicle, $D_{l}$ denotes the maximum deceleration of the $l$-th vehicle;

4: for $j\in[1,K]$ do

5: if $CS_{l}\cup CS_{l+1}==1$ then $a_{l}(j+1)=0$, $v_{l}(j+1)=0$,
$x_{l}(j+1)=x_{l}(j)$; else perform the fourth-order Runge-Kutta
discretization of the vehicle dynamics according to (14); end if

6: if $x_{l}[j+1]\geq x_{l-1}[j+1]$ & $CS_{l}==0$ then $CS_{l}=1$,
$RV_{l}=v_{l}[j+1]-v_{l-1}[j+1]$;

7: end if

8: end for

9: if $\bigcup\limits_{l=1,\cdots,N}CS_{l}==1$ then $CN++$;

10: end if

11: Compute $CS(i)=\sum\limits_{l=1}^{N}CS_{l}$;
$RV(i)=\sum\limits_{l=1}^{N}RV_{l}$;

12: if $CS(i)\geq 1$ then compute $severity(i)=RV(i)/CS(i)$;

13: end if

14: end for

15: Output the probability of collision as $\mathbb{P}=CN/n$, the expected
number of collisions as $\mathbb{N}=\sum\limits_{i=1}^{n}CS(i)/n$, and the
relative velocity at impact as
$\mathbb{S}=\sum\limits_{i=1}^{n}severity(i)/n$.

##  IV SIMULATION RESULTS AND DISCUSSIONS

In this section, we present a numerical example to perform the simulation
algorithm achieved in Section III. We consider the following numerical values
for the system parameters: $N=10$, $\tau_{0}=0.5$ seconds, $d=2,4,6$ m,
respectively. In the numerical simulation, $\tau$ was chosen as
$\tau=\tau_{0}$. The initial steady-state velocity for the $i$-th vehicle is
assumed to be $\bar{v}_{i}=25~{}{\rm m/s}$. The number of iterations is chosen
to be $n=2000$, and the simulation time as $50$ seconds with the
discretization step $h=0.01$ seconds. We consider the maximum deceleration of
the $i$-th vehicle $D_{i}\in[4.75,9.75]$ with the probability distribution as
given in Fig. 3.

Figure 3: The probability distribution of the maximum deceleration [18].

Choose $k_{a}=0.2$, $h_{w}=0.86$, then the admissible regions of $k_{v}$ and
$k_{p}$ for $r=1,2,3,4$ are shown in Fig. 4.

Figure 4: The admissible regions of $k_{v}$ and $k_{p}$.

In an emergency braking scenario, collision avoidance is a key objective.
Thus, we choose the control gains and time headway for the CACC+ case ($r>1$)
to be the same as that of the CACC case ($r=1$) with $k_{v}=0.92$,
$k_{p}=0.03$, guaranteeing a fair comparison between CACC and CACC+. Before
proceeding with this, safety metrics for the case without coordination, i.e.,
all vehicles brake with the maximum deceleration, are provided in TABLE I.
Note that collision avoidance without coordination may be ensured only in
limited cases such as $D_{0}<D_{1}<D_{2}<...<D_{10}$; since we have 11
discretized values of $D_{i}$, the probability of collision avoidance in this
case is near zero; to see this, let $p_{1}=\mathbb{P}\\{D_{0}=\hat{D}_{1}\\}$,
$p_{2}=\mathbb{P}\\{D_{1}=\hat{D}_{2}\\}$, $\cdots$; since the set
$[\hat{D}_{1},\cdots,\hat{D}_{11}]$ has 11 values, the probability of
collision avoidance without coordination is given by
$\mathbb{P}\\{D_{0}<D_{1}<...<D_{10}\\}=\prod_{j=1}^{11}p_{j}$, which is near
zero. Therefore, the probability of collision without coordination is almost
1.

TABLE I: The safety metrics for the case without coordination ($d=6~{}{\rm m}$) $D_{0}$ | 4.75 | 5.25 | 5.75 | 6.25 | 6.75 | 7.25 | 7.75 | 8.25 | 8.75 | 9.25 | 9.75
---|---|---|---|---|---|---|---|---|---|---|---
$\mathbb{P}$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
$\mathbb{N}$ | 6.1680 | 6.2405 | 6.2080 | 6.2150 | 6.2085 | 6.1970 | 6.2345 | 6.2440 | 6.2125 | 6.1940 | 6.2350
$\mathbb{S}$ | 22.5985 | 22.5913 | 22.4154 | 22.7564 | 22.6850 | 22.7315 | 22.8060 | 22.8738 | 22.7030 | 22.5595 | 22.9056

To demonstrate the effectiveness of coordination in reducing the three safety
metrics, we consider the following cases $r=1$ (CACC), $r=2$ (CACC+), and
$r=3$ (CACC+) with three different standstill spacing $d=2$ m, $d=4$ m, and
$d=6$ m.

First, when the standstill spacing $d=2$ m, the probability of collision, the
expected number of collisions, and the relative velocity at impact are
provided in Fig. 5, Fig. 6, and Fig. 7, respectively.

Figure 5: The probability of collision when $d=2$ m.  Figure 6: The expected
number of collisions when $d=2$ m.  Figure 7: The relative velocity at impact
when $d=2$ m.

Second, when the standstill spacing $d=4$ m, the probability of collision, the
expected number of collisions, and the relative velocity at impact,
respectively, are provided in Fig. 8, Fig. 9, and Fig. 10.

Figure 8: The probability of collision when $d=4$ m.  Figure 9: The expected
number of collisions when $d=4$ m.  Figure 10: The relative velocity at impact
when $d=4$ m.

In addition, when the standstill spacing $d=6$ m, the probability of
collision, the expected number of collisions, and the relative velocity at
impact, respectively, are provided in Fig. 11, Fig. 12, and Fig. 13.

Figure 11: The probability of collision when $d=6$ m.  Figure 12: The expected
number of collisions when $d=6$ m.  Figure 13: The relative velocity at impact
when $d=6$ m.

From the above simulation results, one can observe that the probability of
collision and the expected number of collisions can be improved under CACC+,
whereas the relative velocity at impact can deteriorate when $D_{0}$ is
greater than a certain value, which may be due to several reasons, such as the
heterogeneous control structure, parameter values, etc.

While the safety metrics can be improved by increasing the standstill spacing,
however, with the increase of the standstill spacing, the vehicle throughput
and connectivity reduce. To evaluate the effectiveness of CACC+ in improving
the safety metrics, the comparison of the probability of collision between the
CACC case with $d=4$ m and $d=6$ m and the CACC+ case ($r=2$) with $d=2$ m and
$d=4$ m is provided in Fig. 14, and the comparison of the expected number of
collisions between the CACC case with $d=4$ m and $d=6$ m and the CACC+ case
($r=2$) with $d=2$ m and $d=4$ m is provided in Fig. 15. It can be seen that
CACC+ can achieve comparable or better performance with a smaller standstill
spacing when compared to CACC.

Figure 14: The benefit of CACC+ in terms of probability of collision.  Figure
15: The benefit of CACC+ in terms of the expected number of collisions.

##  V CONCLUSION

In this paper, we have provided a new approach to assess safety benefits of
cooperative adaptive cruise control systems with different information
topologies in connected and autonomous vehicles. We have compared CACC and
CACC+ under emergency braking scenarios with safety metrics given by the
probability of collision, the expected number of collisions, and the relative
velocity at impact. By varying the standstill spacing, we found larger
standstill spacing can render better safety performance, and using CACC+ with
a smaller standstill spacing can maintain a comparable safety performance than
CACC. Topics of future work include safety implications when there are packet
losses in communicated information, communication delay, noise, effect of
control gains and time headway.

## References

  * [1] S. Darbha, S. Konduri, and P. R. Pagilla, “Benefits of V2V communication for autonomous and connected vehicles,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 5, pp. 1954–1963, 2018.
  * [2] H. T. Mouftah, M. Erol-Kantarci, and S. Sorour, _Connected and Autonomous Vehicles in Smart Cities_. CRC Press, 2020\.
  * [3] A. Papadoulis, M. Quddus, and M. Imprialou, “Evaluating the safety impact of connected and autonomous vehicles on motorways,” _Accident Analysis & Prevention_, vol. 124, pp. 12–22, 2019.
  * [4] J. B. Kenney, “Dedicated short-range communications (DSRC) standards in the United States,” _Proceedings of the IEEE_ , vol. 99, no. 7, pp. 1162–1182, 2011.
  * [5] A. Vinel, L. Lan, and N. Lyamin, “Vehicle-to-vehicle communication in c-acc/platooning scenarios,” _IEEE Communications Magazine_ , vol. 53, no. 8, pp. 192–197, 2015.
  * [6] M. H. C. Garcia, A. Molina-Galan, M. Boban, J. Gozalvez, B. Coll-Perales, T. Şahin, and A. Kousaridas, “A tutorial on 5g nr v2x communications,” _IEEE Communications Surveys & Tutorials_, vol. 23, no. 3, pp. 1972–2026, 2021.
  * [7] S. Darbha, S. Konduri, and P. R. Pagilla, “Vehicle platooning with constant spacing strategies and multiple vehicle look ahead information,” _IET Intelligent Transport Systems_ , vol. 14, no. 6, pp. 589–600, 2020.
  * [8] V. Vegamoor, S. Rathinam, and S. Darbha, “String stability of connected vehicle platoons under lossy v2v communication,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 7, pp. 8834–8845, 2021.
  * [9] J. Ploeg, D. P. Shukla, N. van de Wouw, and H. Nijmeijer, “Controller synthesis for string stability of vehicle platoons,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 15, no. 2, pp. 854–865, 2014.
  * [10] J. Ploeg, N. van de Wouw, and H. Nijmeijer, “Lp string stability of cascaded systems: Application to vehicle platooning,” _IEEE Transactions on Control Systems Technology_ , vol. 22, no. 2, pp. 786–793, 2014.
  * [11] B. Besselink and K. H. Johansson, “String stability and a delay-based spacing policy for vehicle platoons subject to disturbances,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 9, pp. 4376–4391, 2017.
  * [12] A. A. Malikopoulos, L. Beaver, and I. V. Chremos, “Optimal time trajectory and coordination for connected and automated vehicles,” _Automatica_ , vol. 125, p. 109469, 2021.
  * [13] S. Feng, Y. Zhang, S. E. Li, Z. Cao, H. X. Liu, and L. Li, “String stability for vehicular platoon control: Definitions and analysis methods,” _Annual Reviews in Control_ , vol. 47, pp. 81–97, 2019.
  * [14] Y. Bian, Y. Zheng, W. Ren, S. E. Li, J. Wang, and K. Li, “Reducing time headway for platooning of connected vehicles via v2v communication,” _Transportation Research Part C: Emerging Technologies_ , vol. 102, pp. 87–105, 2019.
  * [15] J. I. Ge and G. Orosz, “Connected cruise control among human-driven vehicles: Experiment-based parameter estimation and optimal control design,” _Transportation Research Part C: Emerging Technologies_ , vol. 95, pp. 445–459, 2018.
  * [16] S. Konduri, P. R. Pagilla, and S. Darbha, “A Combinatorial Approach for Developing Ring Communication Graphs for Vehicle Formations,” _Journal of Dynamic Systems, Measurement, and Control_ , vol. 139, no. 10, 06 2017.
  * [17] Y. Kim, “String stability margin of cyclic vehicle platoons with variable communication range,” _Automatica_ , vol. 146, p. 110488, 2022.
  * [18] D. N. Godbole and J. Lygeros, “Tools for safety-throughput analysis of automated highway systems,” in _Proceedings of the 1997 American Control Conference (Cat. No. 97CH36041)_ , vol. 3. IEEE, 1997, pp. 2031–2035.
  * [19] V. K. Vegamoor, S. Darbha, and K. R. Rajagopal, “A review of automatic vehicle following systems,” _Journal of the Indian Institute of Science_ , vol. 99, pp. 567–587, 2019.
  * [20] S. Darbha and W. Choi, “A methodology for assessing the benefits of coordination on the safety of vehicles,” _Journal of Intelligent Transportation Systems_ , vol. 16, no. 2, pp. 70–81, 2012.
  * [21] S. Darbha and K. Rajagopal, “A methodology to assess the safety of automatically controlled vehicles,” _International Journal of Advances in Engineering Sciences and Applied Mathematics_ , vol. 5, pp. 87–93, 2013.
  * [22] W. Choi and D. Swaroop, “Assessing the safety benefits due to coordination amongst vehicles during an emergency braking maneuver,” in _Proceedings of the 2001 American Control Conference.(Cat. No. 01CH37148)_ , vol. 3. IEEE, 2001, pp. 2099–2104.
  * [23] W. Choi and S. Darbha, “Assessing the benefits of coordination in automatically controlled vehicles,” in _ITSC 2001. 2001 IEEE Intelligent Transportation Systems. Proceedings (Cat. No. 01TH8585)_. IEEE, 2001, pp. 70–75.
  * [24] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” _The collected works of Wassily Hoeffding_ , pp. 409–426, 1994\.


# Group Testing using left-and-right-regular sparse-graph codes

Avinash Vem, Nagaraj T. Janakiraman, Krishna R. Narayanan
Department of Electrical and Computer Engineering
Texas A&M University
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of non-adaptive group testing of $N$ items out of
which $K$ or less items are known to be defective. We propose a testing scheme
based on left-and-right-regular sparse-graph codes and a simple iterative
decoder. We show that for any arbitrarily small $\epsilon>0$ our scheme
requires only $m=c_{\epsilon}K\log\frac{c_{1}N}{K}$ tests to recover
$(1-\epsilon)$ fraction of the defective items with high probability (w.h.p)
i.e., with probability approaching $1$ asymptotically in $N$ and $K$, where
the value of constants $c_{\epsilon}$ and $\ell$ are a function of the desired
error floor $\epsilon$ and constant $c_{1}=\frac{\ell}{c_{\epsilon}}$
(observed to be approximately equal to 1 for various values of $\epsilon$).
More importantly the iterative decoding algorithm has a sub-linear
computational complexity of $\mathcal{O}(K\log\frac{N}{K})$ which is known to
be optimal. Also for $m=c_{2}K\log K\log\frac{N}{K}$ tests our scheme recovers
the whole set of defective items w.h.p. These results are valid for both
noiseless and noisy versions of the problem as long as the number of defective
items scale sub-linearly with the total number of items, i.e., $K=o(N)$. The
simulation results validate the theoretical results by showing a substantial
improvement in the number of tests required when compared to the testing
scheme based on left-regular sparse-graphs.

##  I Introduction

The problem of Group Testing (GT) refers to testing a large population of $N$
items for $K$ defective items (or sick people) where grouping multiple items
together for a single test is possible. The output of the test is negative if
all the grouped items are non-defective or else the output is positive. In the
scenario when $K\ll N$, the objective of GT is to design the testing scheme
such that the total number of tests $m$ to be performed is minimized.

This problem was first introduced to the field of statistics by Dorfman [1]
during World War II for testing the soldiers for syphilis without having to
test each soldier individually. Since then group testing has found application
in wide variety of problems like clone library screening, non-linear
optimization, multi-access communication etc.., [2] and fields like
biology[3], machine learning[4], data structures[5] and signal processing[6].
A comprehensive survey on group testing algorithms, both combinatorial and
probabilistic, can be found in [2, 7, 8].

In the literature on Group Testing, three kinds of reconstruction guarantees
have been considered: combinatorial, probabilistic and approximate. In the
combinatorial designs for the GT problem, the probability of recovery for any
given defective set should be equal to $1$ whereas in the probabilistic
version one is interested in recovering all the defective items with high
probability (w.h.p) i.e., with probability approaching $1$ asymptotically in
$N$ and $K$. Another variant of the probabilistic version is that the
probability of recovery is required to be greater than or equal to
$(1-\varepsilon)$ for a given $\varepsilon>0$. For the approximate recovery
version one is interested in only recovering a $(1-\epsilon)$ fraction of the
defective items (not the whole set of defective items) w.h.p.

For the combinatorial GT the best known lower bound on the number of tests
required is $\Omega(K^{2}\frac{\log N}{\log K})$ [9, 10] whereas the best
known achievability bound is $\mathcal{O}(K^{2}\log N)$ [11, 12]. Most of
these results were based on algorithms relying on exhaustive searches thus
have a high computational complexity of atleast $\mathcal{O}(K^{2}N\log N)$.
Only recently a scheme with efficient decoding was proposed by Indyk et al.,
[13] where all the defective items are guaranteed to recover using
$m=\mathcal{O}(K^{2}\log N)$ tests in
$\text{poly}(K)\cdot\mathcal{O}(m\log^{2}m)+\mathcal{O}(m^{2})$ time.

If we consider the probabilistic version of the problem, it was shown in [7,
8] that the number of tests necessary is $\Omega(K\log\frac{N}{K})$ which is
the best known lower bound in the literature. And regarding the best known
achievability bound Mazumdar [14] proposed a construction that has an
asymptotically decaying error probability with
$\mathcal{O}(K\frac{\log^{2}N}{\log K})$ tests. For the approximate version it
was shown [8] that the required number of tests scale as $\mathcal{O}(K\log
N)$ and to the best of our knowledge this is the tightest bound known.

In [15] authors Lee, Pedarsani and Ramchandran proposed a testing scheme based
on left-regular sparse-graph codes and a simple iterative decoder based on
thepeeling decoder, which are popular tools in channel coding [16], for the
non-adaptive group testing problem. They refer to the scheme as
SAFFRON(Sparse-grAph codes Framewrok For gROup testiNg), a reference which we
will follow through this document. The authors proved that using SAFFRON
scheme $m=c_{\epsilon}K\log N$ number of tests are enough to identify atleast
$(1-\epsilon)$ fraction of defective items (the approximate version of GT)
w.h.p. The precise value of constant $c_{\epsilon}$ as a function of the
required error floor $\epsilon$ is also given. More importantly the
computational complexity of the proposed peeling based decoder is only
$\mathcal{O}(K\log N)$. They also showed that with $m=c\cdot K\log K\log N$
tests i.e. with an additional $\log K$ factor, the whole defective set (the
probabilistic version of GT) can be recovered with an asymptotically high
probability of $1-\mathcal{O}(K^{-\alpha})$.

### Our Contributions

In this work, we propose a non-adaptive GT scheme that is similar to the
SAFFRON but we employ left-and-right-regular sparse-graph codes instead of the
left-regular sparse-graph codes and show that we only require
$c_{\epsilon}K\log\frac{N\ell}{c_{\epsilon}K}$ number of tests for an error
floor of $\epsilon$ in the approximate version of the GT problem. Although the
testing complexity of our scheme has the same asymptotic order
$\mathcal{O}(K\log N)$ as that of [15], which as far as we are aware is the
best known order result for the required number of tests in the approximate
GT, it provides a better explicit upper bound of $\Theta(K\log\frac{N}{K})$
with optimal computational complexity $\mathcal{O}(K\log\frac{N}{K})$ and also
a significant improvement in the required number of tests for finite values of
$K,N$. Following the approach in [15] we extend our proposed scheme with the
singleton-only variant of the decoder to tackle the probabilistic version of
the GT problem. In Sec. V we show that for $m=c\cdot K\log K\log\frac{N}{K}$
tests i.e. with an additional $\log K$ factor the whole defective set can be
recovered w.h.p. Note that the testing complexity of our scheme is only $\log
K$ factor away from the best known lower bound of $\Omega(K\log\frac{N}{K})$
[7] for the probabilistic GT problem. We also extend our scheme to the noisy
GT problem, where the test results are corrupted by noise, using an error-
correcting code similar to the approach taken in [15]. We demonstrate the
improvement in the required number of tests due to _left-_ and-_right_
-regular graphs for finite values of $K,N$ via simulations.

##  II Problem Statement

Formally the group testing problem can be stated as following. Given a total
number of $N$ items out of which $K$ are defective, the objective is to
perform $m$ different tests and identify the location of the $K$ defective
items from the test outputs. For now we consider only the noiseless group
testing problem i.e., the result of each test is exactly equal to the boolean
OR of all the items participating in the test.

Let the support vector $\mathbf{x}\in\\{0,1\\}^{N}$ denote the list of items
in which the indices with non-zero values correspond to the defective items. A
non-adaptive testing scheme consisting of $m$ tests can be represented by a
matrix $\mathbf{A}\in\\{0,1\\}^{m\times N}$ where each row $\mathbf{a}_{i}$
corresponds to a test. The non-zero indices in row $\mathbf{a}_{i}$ correspond
to the items that participate in $i^{\text{th}}$ test. The output
corresponding to vector $\mathbf{x}$ and the testing scheme $\mathbf{A}$ and
can be expressed in matrix form as:

$\mathbf{y}=\mathbf{A\odot x}$

where $\odot$ is the usual matrix multiplication in which the arithmetic
multiplications are replaced by the boolean AND operation and the arithmetic
additions are replaced by the boolean OR operation.

##  III Review: SAFFRON

As mentioned earlier the SAFFRON scheme [15] is based on left-regular sparse
graph codes and is applied for non-adaptive group testing problem. In this
section we will briefly review their testing scheme, iterative decoding scheme
(reconstruction of $\mathbf{x}$ given $\mathbf{y}$) and their main results.
The SAFFRON testing scheme consists of two stages: the first stage is based on
a left-regular sparse graph code which pools the $N$ items into $M$ non-
disjoint bins where each item belongs to exactly $\ell$ bins. The second stage
comprises of producing $h$ testing outputs at each bin where the $h$ different
combinations of the pooled items (from the first stage) at the respective bin
are defined according to a universal signature matrix. For the first stage the
authors consider a bipartite graph with $N$ variable nodes (corresponding to
the $N$ items) and $M$ bin nodes. Each variable node is connected to $\ell$
bin nodes chosen uniformly at random from the $M$ available bin nodes. All the
variable nodes (historically depicted on the left side of the graph in coding
theory) have a degree $\ell$, hence the left-regular, whereas the degree of a
bin node on the right is a random variable in the range $[0:N]$.

######  Definition 1 (Left-regular sparse graph ensemble).

Let $\mathcal{G}_{\ell}(N,M)$ be the ensemble of left-regular bipartite graphs
where for each variable node the $\ell$ right node connections are chosen
uniformly at random from the $M$ right nodes.

Let $\mathbf{T}_{G}\in\\{0,1\\}^{M\times N}$ be the adjacency matrix
corresponding to a graph $G\in\mathcal{G}_{\ell}(N,M)$ i.e., each column in
$\mathbf{T}_{G}$ corresponds to a variable node and has exactly $\ell$ ones.
Let the rows in matrix $\mathbf{T}_{G}$ be given by
$\mathbf{T}_{G}=[\mathbf{t}^{T}_{1},\mathbf{t}^{T}_{2},\dots,\mathbf{t}^{T}_{M}]^{T}$.
For the second stage let the universal signature matrix defining the $h$ tests
at each bin be $\mathbf{U}\in\\{0,1\\}^{h\times N}$. Then the overall testing
matrix
$\mathbf{A}\mathrel{\mathop{:}}=[\mathbf{A}_{1}^{T},\ldots,\mathbf{A}_{M}^{T}]^{T}$
where $\mathbf{A}_{i}=\mathbf{U}\operatorname{diag}(\mathbf{t}_{i})$ of size
$h\times N$ defines the $h$ tests at $i^{\text{th}}$ bin. Thus the total
number of tests is $m=M\times h$.

The signature matrix $\mathbf{U}$ in a more general setting with parameters
$r$ and $p$ can be given by

$\displaystyle\mathbf{U}_{r,p}=\begin{bmatrix}\mathbf{b}_{1}&\mathbf{b}_{2}&\cdots&\mathbf{b}_{r}\\\
\overline{\mathbf{b}}_{1}&\overline{\mathbf{b}}_{2}&\cdots&\overline{\mathbf{b}}_{r}\\\
\mathbf{b}_{\pi^{1}_{1}}&\mathbf{b}_{\pi^{1}_{2}}&\cdots&\mathbf{b}_{\pi^{1}_{r}}\\\
\overline{\mathbf{b}}_{\pi^{1}_{1}}&\overline{\mathbf{b}}_{\pi^{1}_{2}}&\cdots&\overline{\mathbf{b}}_{\pi^{1}_{r}}\\\
\cdots&&\vdots\\\
\mathbf{b}_{\pi^{p-1}_{1}}&\mathbf{b}_{\pi^{p-1}_{2}}&\cdots&\mathbf{b}_{\pi^{p-1}_{r}}\\\
\overline{\mathbf{b}}_{\pi^{p-1}_{1}}&\overline{\mathbf{b}}_{\pi^{p-1}_{2}}&\cdots&\overline{\mathbf{b}}_{\pi^{p-1}_{r}}\end{bmatrix}$
(1)

where $\mathbf{b}_{i}\in\\{0,1\\}^{\lceil{\log_{2}r}\rceil}$ is the binary
expansion vector for $i$ and $\overline{\mathbf{b}}_{i}$ is the complement of
$\mathbf{b}_{i}$.
$\mathbf{\pi}^{k}=[\pi^{k}_{1},\pi^{k}_{2},\ldots,\pi^{k}_{r}]$ denotes a
permutation chosen at random from symmetric group $S_{r}$. Henceforth
$\mathbf{U}_{r,p}$ will refer to either the ensemble of matrices generated
over the choices of the permutations $\pi^{k}$ for $k\in[1:p-1]$ or a matrix
picked uniformly at the random from the said ensemble. The reference should be
sufficiently clear from the context. In the SAFFRON scheme the authors
employed a signature matrix from $\mathbf{U}_{r,p}$ with $r=N$ and $p=3$ thus
resulting in a $\mathbf{U}$ of size $h\times N$ with $h=6\log_{2}N$.

### Decoding

Before describing the decoding process let us review some terminology. A bin
is referred to as a singleton if there is exactly one non-zero variable node
connected to the bin and similarly referred to as a double-ton in case of two
non-zero variable nodes. In the case where we know the identity of one of them
leaving the decoder to decode the identity of the other one, the bin is
referred to as a resolvable double-ton. And if the bin has more than two non-
zero variable nodes attached we refer to it as a multi-ton. First part of the
decoder which is referred to as bin decoder will be able to detect and decode
exactly the identity of the non-zero variable nodes connected to the bin if
and only if the bin is a singleton or a resolvable double-ton. If the bin is a
multi-ton the bin decoder will detect it neither as a singleton nor a
resolvable double-ton with high probability. The second part of the decoder
which is commonly referred to as peeling decoder [17], when given the
identities of some of the non-zero variable nodes by the bin decoder,
identifies the bins connected to the recovered variable nodes and looks for
newly uncovered resolvable double-ton in these bins. This process of
recovering new non-zero variable nodes from already discovered non-zero
variable nodes proceeds in an iterative manner (referred to as peeling off
from the graph historically). For details of the decoder we refer the reader
to [15].

The overall group testing decoder comprises of these two decoders working in
conjunction as follows. In the first and foremost step, given the $m$ tests
output, the bin decoder is applied on the $M$ bins and the set of variable
nodes that are connected to singletons are decoded and output. We denote the
decoded set of non-zero variable nodes as $\mathcal{D}$. Now in an iterative
manner, at each iteration, a variable node from $\mathcal{D}$ is considered
and the bin decoder is applied on the bins connected to this variable node.
The main idea is that if one of these bins is detected as a resolvable double-
ton thus resulting in decoding a new non-zero variable node. The considered
variable node in the previous iteration is moved from $\mathcal{D}$ to a set
of peeled off variable nodes $\mathcal{P}$ and the newly decoded non-zero
variable node in the previous iteration, if any, will be placed in set
$\mathcal{D}$ and continue to the next iteration. The decoder is terminated
when $\mathcal{D}$ is empty and is declared successful if the set
$\mathcal{P}$ equals the set of defective items.

######  Remark 2.

Note that we are not literally peeling off the decoded nodes from the graph
because of the non-linear OR operation on the non-zero variable nodes at each
bin thus preventing us in subtracting the effect of the non-zero node from the
measurements of the bin node unlike in the problems of compressed sensing or
LDPC codes on binary erasure channel.

Now we state the series of lemmas and theorems from [15] that enabled the
authors to show that their SAFFRON scheme with the described peeling decoder
solves the group testing problem with $c\cdot K\log N$ tests and
$\mathcal{O}(K\log N)$ computational complexity.

######  Lemma 3 (Bin decoder analysis).

For a signature matrix $\mathbf{U}_{r,p}$ as described in (1), the bin decoder
successfully detects and resolves if the bin is either a singleton or a
resolvable double-ton. In the case of the bin being a multi-ton, the bin
decoder declares a wrong hypothesis of either a singleton or a resolvable
double-ton with a probability no greater than $\frac{1}{r^{p-1}}$.

###### Proof.

This result was proved in [15] for the choice of parameters $r=N$ and $p=3$.
The extension of the result to general $r,p$ parameters is straight forward. ∎

For convenience the performance of the peeling decoder is analyzed
independently of the bin decoder i.e., a peeling decoder is considered which
assumes that the bin decoder is working accurately which will be referred to
as oracle based peeling decoder. Another simplification is that a pruned graph
is considered where all the zero variable nodes and their respective edges are
removed from the graph. Also the oracle based peeling decoder is assumed to
decode a variable node if it is connected to a bin node with degree one or
degree two with one of them already decoded, in an iterative fashion. Any
right node with more than degree two is untouched by this oracle based peeling
decoder. It is easy to verify that the original decoder with accurate bin
decoding is equivalent to this simplified oracle based peeling decoder on a
pruned graph.

######  Definition 4 (Pruned graph ensemble).

Let the pruned graph ensemble $\tilde{\mathcal{G}}_{l}(N,K,M)$ be the set of
all bipartite graphs obtained from removing a random $N-K$ subset of variable
nodes from a graph from the ensemble $\mathcal{G}_{\ell}(N,M)$. Note that
graphs from the pruned ensemble have $K$ variable nodes.

Before we analyze the pruned graph ensemble let us define the right-node
degree distribution (d.d) of an ensemble as $R(x)=\sum_{i}R_{i}x^{i}$ where
$R_{i}$ is the probability that a right-node in any graph from the ensemble
has degree $i$. Similarly the edge d.d $\rho(x)=\sum_{i}\rho_{i}x^{i-1}$ is
defined where $\rho_{i}$ is the probability that a random edge in the graph is
connected to a right-node of degree $i$. Note that the left-degree
distribution is regular (i.e. $L(x)=x^{\ell}$) even for the pruned graph
ensemble and hence is not specifically discussed.

######  Lemma 5 (Edge d.d of Pruned graph).

For the pruned ensemble $\tilde{\mathcal{G}}_{\ell}(N,K,M)$, it was shown that
in the limit $K,N\rightarrow\infty$, $\rho_{1}=e^{-\lambda}$ and
$\rho_{2}=\lambda e^{-\lambda}$ where $\lambda=\ell/c_{\epsilon}$ for
$M=c_{\epsilon}K$ for any constant $c_{\epsilon}$.

######  Lemma 6.

For the pruned graph ensemble $\tilde{\mathcal{G}}_{\ell}(N,K,M)$ the oracle-
based peeling decoder fails to peel off atleast $(1-\epsilon)$ fraction of the
variable nodes with exponentially decaying probability if $M\geq
c_{\epsilon}K$ where the required $c_{\epsilon}$ and $\ell$ for various values
of $\epsilon$ are given in Table. I.

###### Proof.

Instead of reworking the whole proof here from [15], we will list the main
steps involved in the proof which we will use further along. Let $p_{j}$ be
the probability that a random defective item is not identified at iteration
$j$ of the decoder, in the limit $N\text{ and }K\rightarrow\infty$. Then one
can write the density evolution (DE) equations relating $p_{j+1}$ to $p_{j}$
as

$\displaystyle p_{j+1}=\left[1-(\rho_{1}+\rho_{2}(1-p_{j}))\right]^{\ell-1}.$

For this DE, we can see that $0$ is not a fixed point and hence
$p_{j}\nrightarrow 0$ as $j\rightarrow\infty$. Therefore numerically
optimizing the values of $c_{\epsilon}$ and $\ell$ such that
$\lim_{j\rightarrow\infty}p_{j}\leq\epsilon$ gives the optimal values for
$c_{\epsilon}$ and $\ell$ given in Table. I. It was also shown [15, 16] that
for such sparse graph systems the actual fraction of the undecoded variable
nodes deviates from the average undecoded fraction of the variable nodes given
by the DE with exponentially low probability. ∎

$\epsilon$ | $10^{-3}$ | $10^{-4}$ | $10^{-5}$ | $10^{-6}$ | $10^{-7}$ | $10^{-8}$ | $10^{-9}$
---|---|---|---|---|---|---|---
$c_{1}(\epsilon)$ | 6.13 | 7.88 | 9.63 | 11.36 | 13.10 | 14.84 | 16.57
$\ell$ | 7 | 9 | 10 | 12 | 14 | 15 | 17
Table I: Constants for various error floor values

Combining the lemmas and remarks above, the main result from [15] can be
summarized as below.

######  Theorem 7.

A random testing matrix from the SAFFRON scheme with
$m=6c_{\epsilon}K\log_{2}N$ tests recovers atleast $(1-\epsilon)$ fraction of
the defective items w.h.p of atleast $1-O(\frac{K}{N^{2}})$. The computational
complexity of the decoding scheme is $O(K\log N)$. The constant $c_{\epsilon}$
is given in Table. I for some values of $\epsilon$.

##  IV Proposed Scheme

The main difference between the SAFFRON scheme described in Sec. III and our
proposed scheme is that we use a left-and-right-regular sparse-graph instead
of left-regular sparse-graph in the first stage for the binning operation.

######  Definition 8 (Left-and-right-regular sparse graph ensemble).

We define $\mathcal{G}_{\ell,r}(N,M)$ to be the ensemble of left-and-right-
regular graphs where the $N\ell$ edge connections from the left and
$Mr(=N\ell)$ edge connections from the right are paired up according to a
permutation $\pi$ chosen at random from $S_{N\ell}$.

Let $\mathbf{T}_{G}\in\\{0,1\\}^{M\times N}$ be the adjacency matrix
corresponding to a graph $G\in\mathcal{G}_{\ell,r}(N,M)$ i.e., each column in
$\mathbf{T}_{G}$ corresponding to a variable node has exactly $\ell$ ones and
each row corresponding to a bin node has exactly $r$ ones. And let the
universal signature matrix be $\mathbf{U}\in\\{0,1\\}^{h\times r}$ chosen from
the $\mathbf{U}_{r,p}$ ensemble. Then the overall testing matrix
$\mathbf{A}\mathrel{\mathop{:}}=[\mathbf{A}_{1}^{T},\ldots,\mathbf{A}_{M}^{T}]^{T}$
where $\mathbf{A}_{i}\in\\{0,1\\}^{h\times N}$ defining the $h$ tests at
$i^{\text{th}}$ bin is given by

$\displaystyle\mathbf{A}_{i}$
$\displaystyle=[\mathbf{0},\ldots,\mathbf{0},\mathbf{u}_{1},\mathbf{0},\ldots,\mathbf{u}_{2},\mathbf{0},\ldots,\mathbf{u}_{r}],\quad\text{where}$
(2) $\displaystyle\mathbf{t}_{i}$ $\displaystyle=[0,\ldots,0,\hskip
2.58334pt1,\hskip 3.87495pt0,\ldots,\hskip 2.58334pt1,\hskip
3.87495pt0,\ldots,\hskip 3.87495pt1].$

Note that $\mathbf{A}_{i}$ is defined by placing the $r$ columns of
$\mathbf{U}$ at the $r$ non-zero indices of $\mathbf{t}_{i}$ and the remaining
are padded with zero columns. We can observe that the total number of tests
for this scheme is $m=M\times h$ where $h=2p\log_{2}r$.

######  Example 9.

Let us look at an example for $(N,M)=(6,3)$ and $(\ell,r)=(2,4)$. Then the
adjacency matrix $\mathbf{T}_{G}$ of a graph $G\in\mathcal{G}_{2,4}(6,3)$ and
a signature matrix $\mathbf{U}\in\\{0,1\\}^{4\times 3}$ for $p=1$ and
$\log_{2}r=2$ are given by

$\mathbf{T}_{G}=\begin{bmatrix}1&1&0&1&0&1\\\ 0&1&1&1&1&0\\\
1&0&1&0&1&1\end{bmatrix}\mathbf{U}=\begin{bmatrix}0&0&1&1\\\ 0&1&0&1\\\
1&1&0&0\\\ 1&0&1&0\end{bmatrix}.$

Then, the measurement matrix $\bf A$ with $m=2pM\lceil{\log_{2}r}\rceil=12$
tests is given by

$\mathbf{A}=\begin{bmatrix}0&0&0&1&0&1\\\ 0&1&0&0&0&1\\\ 1&1&0&0&0&0\\\
1&0&0&1&0&0\\\ 0&0&0&1&1&0\\\ 0&0&1&0&1&0\\\ 0&1&1&0&0&0\\\ 0&1&0&1&0&0\\\
0&0&0&0&1&1\\\ 0&0&1&0&0&1\\\ 1&0&1&0&0&0\\\ 1&0&0&0&1&0\\\ \end{bmatrix}$

$\ell$$\vdots$$N$ vars$r\leq N$$\vdots$$c_{1}K$
bins$\pi$$\mathbf{U}\in\\{0,1\\}^{c\log N\times N}$$\log N$
tests$M=\Theta(K\log N)$ $\ell$$\vdots$$N$
vars$r=\frac{N\ell}{c_{1}K}$$\vdots$$c_{1}K$
bins$\pi$$\mathbf{U}\in\\{0,1\\}^{c\log r\times r}$$\log r$
tests$M=\Theta(K\log\frac{N}{K})$

Figure 1: Illustration of the main differences between SAFFRON [15] on the
left and our regular-SAFFRON scheme on the right. In both the schemes the
peeling decoder on sparse graph requires $\Theta(K)$ bins. But for the bin
decoder part, in SAFFRON scheme the right degree is a random variable with a
maximum value of $N$ and thus requires $\Theta(\log N)$ tests at each bin.
Whereas our scheme based on right-regular sparse graph has a constant right
degree of $\Theta(\frac{N}{K})$ and thus requires only
$\Theta(\log\frac{N}{K})$ tests at each bin. Thus we can improve the number of
tests from $\Theta(K\log N)$ to $\Theta(K\log\frac{N}{K})$.

######  Definition 10 (Regular-SAFFRON).

Let the ensemble of testing matrices be
$\mathcal{G}_{\ell,r}(N,M)\times\mathbf{U}_{r,p}$ where a graph $G$ from
$\mathcal{G}_{\ell,r}(N,M)$ and a signature matrix $\mathbf{U}$ from
$\mathbf{U}_{r,p}$ are chosen at random and the testing matrix $\mathbf{A}$ is
defined according to Eq. (2). Note that the total number of tests is
$2pM\log_{2}r$ where $r=\frac{N\ell}{M}$.

For the regular-SAFFRON testing ensemble defined in Def. 10, we employ the
iterative decoder described in Sec. III. Similar to the SAFFRON scheme we will
analyze the peeling decoder and the bin decoder separately and union bound the
total error probability of the decoding scheme. As we have already mentioned
the analysis of just the peeling decoder part can be carried out by
considering a simplified oracle-based peeling decoder on a pruned graph with
only the non-zero variable nodes remaining.

######  Definition 11 (Pruned graph ensemble).

We will define the pruned graph ensemble $\tilde{\mathcal{G}}_{\ell,r}(N,K,M)$
as the set of all graphs obtained from removing a random $N-K$ subset of
variable nodes from a graph from left-and-right-regular sparse-graph ensemble
$\mathcal{G}_{\ell,r}(N,M)$.

Note that graphs from the pruned ensemble have $K$ variable nodes with a
degree $\ell$ whereas the right degree is not regular anymore.

######  Lemma 12 (Edge d.d of pruned graph).

For the pruned graph ensemble $\tilde{\mathcal{G}}_{\ell,r}(N,K,M)$ it can be
shown in the limit $K,N\rightarrow\infty$ and $K=o(N)$ that the edge d.d
coefficients approach $\rho_{1}=e^{-\lambda}$ and $\rho_{2}=\lambda
e^{-\lambda}$ where $\lambda=\ell/c$ for the choice of $M=cK$, $c$ being some
constant.

###### Proof.

We will first derive $R(x)$ for the pruned graph ensemble and then use the
relation $\rho(x)=\frac{R^{\prime}(x)}{R^{\prime}(1)}$[16] to derive the edge
d.d. Note that all the bin nodes have a uniform degree $r$ before pruning. In
the pruning operation we are removing a $N-K$ subset of variable nodes at
random which means from the bin node perspective, in an asymptotic sense, this
is equivalent to removing each connected edge with a probability $1-\beta$
where $\beta\mathrel{\mathop{:}}=\frac{K}{N}$. Under this process the right-
node d.d can be written as

$\displaystyle R_{1}$ $\displaystyle=r\beta(1-\beta)^{r-1},\quad\text{ and
similarly}$ (3) $\displaystyle R_{i}$
$\displaystyle=\binom{r}{i}\beta^{i}(1-\beta)^{r-i}\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i<=r$

thus giving us $R(x)=(\beta x+(1-\beta))^{r}$. This gives us

$\displaystyle\rho(x)$ $\displaystyle=\frac{r\beta(\beta
x+(1-\beta))^{r-1}}{r\beta}$ $\displaystyle=(\beta x+(1-\beta))^{r-1}.$

Thus we can compute that $\rho_{1}=(1-\beta)^{r-1}$ and
$\rho_{2}=(r-1)\beta(1-\beta)^{r-2}$. For $M=cK$ we evaluate these quantities
in the limit $K,N\rightarrow\infty$ as

$\displaystyle\lim_{K,N\rightarrow\infty}\rho_{1}$
$\displaystyle=\lim_{K,N\rightarrow\infty}\left(1-\frac{K}{N}\right)^{\frac{N\ell}{cK}-1}$
$\displaystyle=e^{-\lambda}\qquad\text{ where }\lambda=\frac{\ell}{c}$

Similarly we can show $\lim_{K,N\rightarrow\infty}\rho_{2}=\lambda
e^{-\lambda}$. ∎

Note that even if our initial ensemble is left-and-right-regular the pruned
graph ensemble has asymptotically the same degree distribution as in the
SAFFRON scheme where the initial ensemble is left-regular.

######  Lemma 13.

For the pruned graph ensemble $\tilde{\mathcal{G}}_{\ell,r}(N,K,M)$ the
oracle-based peeling decoder fails to peel off atleast $(1-\epsilon)$ fraction
of the variable nodes with exponentially decaying probability for
$M=c_{\epsilon}K$ where $\ell,c_{\epsilon}$ for various $\epsilon$ is given in
Table. I.

###### Proof.

We showed in Lemma. 12 that, in the limit of $K,N\rightarrow\infty$, the edge
degree distribution coefficients $\rho_{1}$ and $\rho_{2}$ approach the same
values as in the SAFFRON scheme (see Lem. 5). Now we follow the exact same
approach as that of Lem. 6 where the limiting values of
$\rho_{1}=e^{-\lambda}$ and $\rho_{2}=\lambda e^{-\lambda}$ are used in the DE
equations to show that for the given values of $\ell$ and $c_{\epsilon}$
$\lim_{j\rightarrow\infty}p_{j}\leq\epsilon$. ∎

######  Theorem 14.

Let $p\in\mathbb{Z}$ such that $K=o(N^{1-1/p})$. A random testing matrix from
the proposed regular SAFFRON ensemble
$\mathcal{G}_{\ell,\frac{N\ell}{c_{\epsilon}K}}(N,c_{\epsilon}K)\times\mathbf{U}_{\frac{N\ell}{c_{\epsilon}K},p}$
with $m=c\cdot K\log_{2}\frac{c_{2}N}{K}$ tests recovers atleast
$(1-\epsilon)$ fraction of the defective items w.h.p. The computational
complexity of the decoding scheme is $\mathcal{O}(K\log\frac{N}{K})$. The
constants are $c=2pc_{\epsilon},c_{2}=\frac{\ell}{c_{\epsilon}}$ where $\ell$
and $c_{\epsilon}$ for various values of $\epsilon$ are given in Table. I.

###### Proof.

It remains to be shown that for the proposed regular SAFFRON scheme the total
probability of error vanishes asymptotically in $K$ and $N$. Let $E_{1}$ be
the event of oracle-based peeling decoder terminating without recovering
atleast $(1-\epsilon)K$ variable nodes. Let $E_{2}$ be the event of the bin
decoder making an error during the entirety of the peeling process and
$E_{\text{bin}}$ be the event of one instance of bin decoder making an error.
The total probability of error $P_{e}$ can be upper bounded by

$\displaystyle P_{e}$ $\displaystyle\leq\text{Pr}(E_{1})+\text{Pr}(E_{2})$
$\displaystyle\leq\text{Pr}(E_{1})+K\ell\text{ Pr}(E_{\text{bin}})$
$\displaystyle\in O\left(\frac{K^{p}}{N^{p-1}}\right)$

where the second inequality is due to the union bound over a maximum of
$K\ell$ (number of edges in the pruned graph) instances of bin decoding. The
third line is due to the fact that $\text{Pr}(E_{1})$ is exponentially
decaying in $K$ (see Lemma. 13) and
$\text{Pr}(E_{\text{bin}})=(\frac{c_{\epsilon}K}{N\ell})^{p-1}$ (see Lemma. 3
and Def. 10) ∎

##  V Total recovery: Singleton-Only Variant

In this section we will look at the proposed regular-SAFFRON scheme but with a
decoder that uses only the singleton bins. To elaborate, the only difference
is in the decoder which is not iterative in this framework and recovers the
variable nodes connected to only the singleton bin nodes and terminates. We
will refer to this scheme as singleton-only regular-SAFFRON scheme. The trade-
off is that we can now recover the whole defective set instead of just a large
fraction of the defective items with an additional $\log K$ factor tests.
Since we do not need to be able to recover resolvable double-tons we only need
$2\log_{2}r$ number of tests at each bin i.e. we choose $p=1$ for the
signature matrix in Eqn. (1).

######  Theorem 15.

Let $K=o(N)$. For $M=c_{\alpha}K\log K$ and $(\ell,r)=(c_{\alpha}\log
K,\frac{N}{K})$ a random testing matrix from the regular SAFFRON ensemble
$\mathcal{G}_{\ell,r}(N,M)\times\mathbf{U}_{r,1}$ with $m=2c_{\alpha}K\log
K\log_{2}\frac{N}{K}$ tests the singleton-only decoder fails to recover all
the non-zero variable nodes with a vanishing probability of
$\mathcal{O}(K^{-\alpha})$ where $c_{\alpha}=e(1+\alpha)$.

###### Proof.

First we observe that for the choice of $(\ell,r)=(c_{\alpha}\log
K,\frac{N}{K})$ number of bins $M=\frac{N\ell}{r}=c_{\alpha}K\log K$ and the
number of tests in each bin is $2\log_{2}\frac{N}{K}$. From Lem. 3 we know
that a singleton bin is guaranteed to be decoded by the bin decoder. Thus it
is enough if we show that for this choice for the number of bins $M$ all the
variable nodes in the pruned graph are connected to atleast one singleton bin
w.h.p of $1-\mathcal{O}(K^{-\alpha})$.

In the pruned graph ensemble, for any particular variable node, the
probability that any of the $\ell$ connected bit nodes are not a singleton can
be given by $(1-R_{1})^{\ell}$ where $R_{1}$ is the probability that a bin
node in the pruned graph ensemble is a singleton. In the limit
$K,N\rightarrow\infty$ the value of $R_{1}$ approaches (from Eq. 3)

$\displaystyle R_{1}$
$\displaystyle=\lim_{K,N\rightarrow\infty}r\beta(1-\beta)^{r-1}$
$\displaystyle=\lim_{\frac{N}{K}\rightarrow\infty}\left(1-\frac{K}{N}\right)^{\frac{N}{K}-1}$
$\displaystyle=e^{-1}$

By using union bound over all the $K$ variable nodes in the pruned graph, the
probability $P_{e}$ that the singleton-only decoder fails to recover a
defective item can be bounded by

$\displaystyle P_{e}$ $\displaystyle\leq K(1-R_{1})^{\ell}$
$\displaystyle=\mathcal{O}\left(K(1-e^{-1})^{e(1+\alpha)\log K}\right)$
$\displaystyle=\mathcal{O}\left(Ke^{-e^{-1}e(1+\alpha)\log K}\right)$
$\displaystyle=\mathcal{O}\left(K^{-\alpha}\right).$

In third line we used $(1-x)\leq e^{-x}$. ∎

##  VI Robust Group Testing

In this section we extend our scheme to the group testing problem where the
test results can be noisy. Formally, the signal model can be described as

$\displaystyle\mathbf{y=A}\odot\mathbf{x+w},$

where $\mathbf{w}\in\\{0,1\\}^{N}$ is an i.i.d. noise vector distributed
according to Bernoulli distribution with parameter $0<q<\frac{1}{2}$ and the
addition is over binary field.

### Testing Scheme

In [15] for the robust group testing problem, the signature matrix used for
noiseless group testing problem is modified using an error control code such
that it can handle singletons and resolvable doubletons in the presence of
noise. The binning operation as defined by the bipartite graph is exactly
identical to that of noiseless case. We describe the modifications to the
signature matrix and the bin detection decoding scheme as given in [15] for
the sake of completeness and then state the performance bounds for our scheme
for the noisy group testing problem.

Let $\mathcal{C}_{n}$ be a binary error-correcting code with the following
definition:

  * •

Let the encoder and decoder functions be
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\frac{n}{R}}$ and
$g:\\{0,1\\}^{\frac{n}{R}}\rightarrow\\{0,1\\}^{n}$ respectively where $R$ is
the rate of the code.

For ease of analysis and tight upper bound for the number of tests we will use
random codes and the optimal maximum-likelihood decoder which gives us the
properties:

  * •

There exists a sequence of codes $\\{\mathcal{C}_{n}\\}$ with the rate of each
code being $R$ satisfying

$\displaystyle
R<1-H(q)-\delta=1+q\log_{2}q+\overline{q}\log_{2}\overline{q}-\delta$ (4)

for any arbitrary small constant $\delta$ such that the probability of error
$\text{Pr}\left(g(\mathbf{x+w})\neq\mathbf{x}\right)<2^{-\kappa n}$ for some
$\kappa>0$. In Eqn. 4, $\overline{q}\mathrel{\mathop{:}}=1-q$.

Even though the computational complexity of using random codes is exponential
in block length of the code since the block length for our application is
$\mathcal{O}(\log\frac{N}{K})$ and hence we have an overall computational
complexity of $\mathcal{O}(N)$. But in practice one can use any of the popular
error-correcting codes such as spatially-coupled LDPC codes or polar codes
which are known to be capacity achieving [18, 19] whose computational
complexity is linear in block length.

The modified signature matrix $\mathbf{U}^{\prime}_{r,p}$ can be described via
$\mathbf{U}_{r,p}$ given in Eq. (1) and encoding function $f$ for
$\mathcal{C}_{n}$ where $n=\lceil{\log_{2}r}\rceil$ as follows:

$\displaystyle\mathbf{U}_{r,p}^{\prime}\mathrel{\mathop{:}}=\begin{bmatrix}f(\mathbf{b}_{1})&f(\mathbf{b}_{2})&\cdots&f(\mathbf{b}_{r})\\\
\overline{f(\mathbf{b}_{1})}&\overline{f(\mathbf{b}_{2})}&\cdots&\overline{f(\mathbf{b}_{r})}\\\
f(\mathbf{b}_{\pi^{1}_{1}})&f(\mathbf{b}_{\pi^{1}_{2}})&\cdots&f(\mathbf{b}_{\pi^{1}_{r}})\\\
\overline{f(\mathbf{b}_{\pi^{1}_{1}})}&\overline{f(\mathbf{b}_{\pi^{1}_{2}})}&\cdots&\overline{f(\mathbf{b}_{\pi^{1}_{r}})}\\\
\cdots&&\vdots\\\
f(\mathbf{b}_{\pi^{p-1}_{1}})&f(\mathbf{b}_{\pi^{p-1}_{2}})&\cdots&f(\mathbf{b}_{\pi^{p-1}_{r}})\\\
\overline{f(\mathbf{b}_{\pi^{p-1}_{1}})}&\overline{f(\mathbf{b}_{\pi^{p-1}_{2}})}&\cdots&\overline{f(\mathbf{b}_{\pi^{p-1}_{r}})}\\\
\end{bmatrix}$ (5)

Then the overall testing matrix $\mathbf{A}$ is defined in identical fashion
to the definition in Sec. III for the case of noiseless case except that
$\mathbf{U}$ will be replaced by $\mathbf{U^{\prime}}$ in Eqn. (5). Formally
it can be defined as
$\mathbf{A}\mathrel{\mathop{:}}=[\mathbf{A}_{1}^{T},\ldots,\mathbf{A}_{M_{1}}^{T}]^{T}$
where $\mathbf{A}_{i}=\mathbf{U^{\prime}}\operatorname{diag}(\mathbf{t}_{i})$
where the binary vectors $\mathbf{t}_{i}$ are defined in Sec. III.

### Decoding

The decoding scheme for the robust group testing, similar to the case of
noiseless case, has two parts with the peeling part of the decoder identical
to that of the noiseless case whereas the bin detection part differs slightly
with an extra step of decoding for the error control code involved.

Given the test output vector at a bin
$\mathbf{y}=[\mathbf{y}^{T}_{01},\mathbf{y}^{T}_{02},\mathbf{y}^{T}_{11},\ldots,\mathbf{y}^{T}_{(p-1)2}]^{T}$,
the bin detection for the noisy case can be summarized as following: The
decoder $\forall i\in[0:p-1]$ applies the decoding function $g(\cdot)$ to the
first segment $\mathbf{y}_{i1}$ in each section $i$ and obtains the location
$l_{i}$ whose binary expansion is equal to the error-correcting decoder output
$g(\mathbf{y}_{i1})$. The decoder then declares the bin as a singleton if
$\pi_{l_{0}}^{i}=l_{i}\leavevmode\nobreak\ \forall i$.

Similarly given that one of the variable nodes connected to the bin is already
decoded to be non-zero, the resolvable double-ton decoding can be summarized
as following. Let the location of the already recovered variable node in the
bin (originally a double-ton) be $l_{0}$ then the test output can be given as

$\displaystyle\begin{bmatrix}\mathbf{y}_{01}\\\ \mathbf{y}_{02}\\\
\mathbf{y}_{11}\\\ \vdots\\\ \mathbf{y}_{p2}\\\
\end{bmatrix}=\mathbf{u}_{l_{0}}\vee\mathbf{u}_{l_{1}}+\mathbf{w}=\begin{bmatrix}f(\mathbf{b}_{l_{0}})\\\
\vspace{2pt}\overline{f(\mathbf{b}_{l_{0}})}\\\
f(\mathbf{b}_{\pi^{1}_{l_{0}}})\\\ \vdots\\\
\overline{f(\mathbf{b}_{\pi^{p}_{l_{0}}})}\\\
\end{bmatrix}\vee\begin{bmatrix}f(\mathbf{b}_{l_{1}})\\\
\vspace{2pt}\overline{f(\mathbf{b}_{l_{1}})}\\\
f(\mathbf{b}_{\pi^{1}_{l_{1}}})\\\ \vdots\\\
\overline{f(\mathbf{b}_{\pi^{p}_{l_{1}}})}\\\
\end{bmatrix}+\begin{bmatrix}\mathbf{w}_{01}\\\ \vspace{2pt}\mathbf{w}_{02}\\\
\mathbf{w}_{11}\\\ \vdots\\\ \mathbf{w}_{p2}\\\ \end{bmatrix}$

where the location of the second non-zero variable node $l_{1}$ needs to be
recovered. Given
$\mathbf{y}=\mathbf{u}_{l_{0}}\vee\mathbf{u}_{l_{1}}+\mathbf{w}$ and
$\mathbf{u}_{l_{0}}$, the first segments of each section in
$\mathbf{u}_{l_{1}}+\mathbf{w}$ can be recovered since for each segment of
$\mathbf{u}_{l_{0}}$ either the vector $f(\mathbf{b}_{\pi^{k}_{l_{0}}})$ or
it’s complement is available. Once the first section
$f(\mathbf{b}_{\pi_{l_{1}}^{i}})+\mathbf{w}$ of each segment $i$ is recovered,
we apply singleton decoding procedure and rules as described above.

######  Lemma 16 (Robust Bin Decoder Analysis).

For a signature matrix $\mathbf{U^{\prime}}_{r,p}$ as described in (5), the
robust bin decoder misses a singleton with probability no greater than
$\frac{p}{r^{\kappa}}$. The robust bin decoder wrongly declares a singleton
with probability no greater than $\frac{1}{r^{p\kappa+p-1}}$.

###### Proof.

Let $E_{i}$ be the event that the error-control decoder $g(\mathbf{y}_{i1})$
commits an error at section $i$. From Eqn. (4) we know that
$\text{Pr}(E_{i})=2^{-\kappa\log r}=r^{-\kappa}$. The robust bin decoder
misses a singleton if the error-control decoder $g(\mathbf{y}_{i1})$ commits
an error at any one section. Thus the probability of missing a singleton can
be upper bounded by applying union bound over all the sections $i\in[0:p-1]$
giving the required result.

Consider a singleton bin and let the event where the robust bin decoder
outputs a singleton hypothesis but the wrong index be $E_{\text{bin}}$. This
event happens when the error-control decoder commits an error and outputs the
exact same wrong index at each and every section. We assume that given the
error-control decoder makes an error, the output is uniformly random among all
the remaining indices. Thus $\text{Pr}(E_{\text{bin}})$ can be upper bounded
by $\frac{1}{r^{\kappa}}(\frac{1}{r^{1+\kappa}})^{p-1}$ which upon
simplification gives us the required result. ∎

The fraction of missed singletons can be compensated by using
$M(1+\frac{p}{r^{\kappa}})$ instead of $M$ such that the total number of
singletons decoded will be
$M(1+\frac{p}{r^{\kappa}})(1-\frac{p}{r^{\kappa}})\approx M$.

######  Theorem 17.

Let $p\in\mathbb{Z}$ such that $K=o\left(N^{1-1/p}\right)$. The proposed
robust regular SAFFRON scheme using $m=c\cdot
K\log_{2}\frac{N\ell}{c_{\epsilon}K}$ tests recovers atleast $(1-\epsilon)$
fraction of the defective items w.h.p. where $c=2p\beta(q)c_{\epsilon}$ and
$\beta(q)=1/R$.

###### Proof.

Similar to the noiseless case the total probability of error $P_{e}$ is
dominated by the performance of bin decoder.

$\displaystyle P_{e}$ $\displaystyle\leq\text{Pr}(E_{1})+K\ell\text{
Pr}(E_{\text{bin}})$
$\displaystyle=\text{Pr}(E_{1})+\mathcal{O}\left(\frac{K^{p+p\kappa}}{N^{p-1+p\kappa)}}\right)$
$\displaystyle=\mathcal{O}\left(\frac{N^{(p-1)(1+\kappa)}}{N^{p-1+p\kappa)}}\right)$
$\displaystyle\in\mathcal{O}(N^{-\kappa})$

where the second line is due to Lem. 16 and the third line is due to the fact
that $\text{Pr}(E_{1})$ is exponentially decaying in $K$ and $K\leq
N^{(p-1)/p}$ for large enough $K,N$. ∎

##  VII Simulation Results

In this section we will evaluate the performance of the proposed regular-
SAFFRON scheme via Monte Carlo simulations and compare it with the results of
SAFFRON scheme provided in [15] for both the noiseless and noisy models.

### Noiseless Group Testing

As per Thm. 14 the proposed regular SAFFRON scheme requires only
$6c_{\epsilon}K\log\frac{N\ell}{c_{\epsilon}K}$ tests as opposed to
$6c_{\epsilon}K\log N$ tests of SAFFRON scheme to recover $(1-\epsilon)$
fraction of defective items with a high probability. We demonstrate this by
simulating the performance for the system parameters summarized below.

  * •

We fix $N=2^{16}$ and $K=100$

  * •

For $\ell\in\\{3,5,7\\}$ we vary the number of bins $M=cK$.

  * •

In Eqn. 1 the parameter $p=2$ is chosen for matrix $\mathbf{U}$

  * •

Thus the bin detection size is $h=6\log_{2}\frac{N\ell}{cK}$

  * •

Hence the total number of tests $m=6cK\log_{2}\left(\frac{N\ell}{cK}\right)$

The results are shown in Fig. 2. We observe that there is clear improvement in
performance for the proposed regular SAFFRON scheme when compared to the
SAFFRON scheme for each $\ell\in\\{3,5,7\\}$.

$100$$200$$300$$400$$500$$600$$700$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$Number
of tests per defective item ($m/K$)Fraction of unidentified
defectives$\ell=3$$\ell=5$$\ell=7$$\ell=3$, regular$\ell=5$,
regular$\ell=7$,regular

Figure 2: MonteCarlo simulations for $K=100,N=2^{16}$. We compare the SAFFRON
scheme [15] with the proposed regular SAFFRON scheme for various left degrees
$\ell\in\\{3,5,7\\}$. The plots in blue indicate the SAFFRON scheme and the
plots in red indicate our regular SAFFRON scheme based on left-and-right-
regular bipartite graphs.

### Noisy Group Testing

Similar to the noiseless group testing problem we simulate the performance of
our robust regular-SAFFRON scheme and compare it with that of the SAFFRON
scheme. For convenience of comparison we choose our system parameters
identical to the choices in [15]. The system parameters are summarized below:

  * •

$N=2^{32},K=2^{7}$. We fix $\ell=12,M=11.36K$

  * •

BSC noise parameter $q\in\\{0.03,0.04,0.05\\}$

  * •

In Eqn. 1 the parameter $p=1$ is chosen for matrix $\mathbf{U}$

  * •

Thus the bin detection size is $h=4\log_{2}\frac{N\ell}{M}$

The results are shown in Fig. 3. Note that for the above set of parameters the
right degree $r=\frac{N\ell}{M}\approx 26$. We choose to operate in field
$GF(2^{7})$ thus giving us a message length of $4$ symbols. For the choice of
code we use a $(4+2e,4)$ Reed-Solomon code for $e\in[0:8]$ thus giving us a
column length of $4\times 7(4+2e)$ bits at each bin and the total number of
tests $m=28M(4+2e)$.

$4$$6$$8$$10$$12$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$Number
of tests ($\times 10^{5}$)Fraction of unidentified
defectivesq=0.03q=0.04q=0.05q=0.03, regularq=0.04, regularq=0.05, regular
Figure 3: MonteCarlo simulations for $K=128,N=2^{32}$. We compare the SAFFRON
scheme with the proposed regular-SAFFRON scheme for a left degree $\ell=12$.
We fix the number of bins and vary the rate of the error control code used.
The plots in blue indicate the SAFFRON scheme[15] and the plots in red
indicate the regular-SAFFRON scheme based on left-and-right-regular bipartite
graphs.

##  VIII Conclusion

We addressed the Group Testing problem for $K$ defective items out of $N$
items. Using left-_and_ -right-regular sparse-graph codes we propose a new
construction for the testing matrix based on that of Lee et al., [15]. We show
that this improves the testing complexity upon the previous results for the
approximate version of the Group Testing problem and achieves asymptotically
vanishing error probability under sub-linear time, order optimal,
computational complexity. We also show that the proposed scheme with a variant
of the original decoder has a testing complexity that is only $\log K$ factor
away from the lower bound for the probabilistic version of the Group Testing
problem with order optimal computational complexity.

## References

  * [1] R. Dorfman, “The detection of defective members of large populations,” The Annals of Mathematical Statistics, vol. 14, no. 4, pp. 436–440, 1943.
  * [2] D.-Z. Du and F. K. Hwang, Combinatorial group testing and its applications, vol. 12.  World Scientific, 1999.
  * [3] H.-B. Chen and F. K. Hwang, “A survey on nonadaptive group testing algorithms through the angle of decoding,” Journal of Combinatorial Optimization, vol. 15, no. 1, pp. 49–59, 2008.
  * [4] D. M. Malioutov and K. R. Varshney, “Exact rule learning via boolean compressed sensing.,” in Proc. Int. Conf. on Machine Learning., pp. 765–773, 2013.
  * [5] M. T. Goodrich, M. J. Atallah, and R. Tamassia, “Indexing information for data forensics,” in International Conference on Applied Cryptography and Network Security, pp. 206–221, Springer, 2005.
  * [6] A. Emad and O. Milenkovic, “Poisson group testing: A probabilistic model for nonadaptive streaming boolean compressed sensing,” in Int. Conf. on Acoustics, Speech & Signal Proc., pp. 3335–3339, IEEE, 2014.
  * [7] C. L. Chan, S. Jaggi, V. Saligrama, and S. Agnihotri, “Non-adaptive group testing: Explicit bounds and novel algorithms,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 3019–3035, 2014.
  * [8] G. K. Atia and V. Saligrama, “Boolean compressed sensing and noisy group testing,” IEEE Trans. Inf. Theory, vol. 58, no. 3, pp. 1880–1901, 2012\.
  * [9] A. G. D’yachkov and V. V. Rykov, “Bounds on the length of disjunctive codes,” Problemy Peredachi Informatsii, vol. 18, no. 3, pp. 7–13, 1982.
  * [10] P. Erdös, P. Frankl, and Z. Füredi, “Families of finite sets in which no set is covered by the union ofr others,” Israel Journal of Mathematics, vol. 51, no. 1, pp. 79–89, 1985.
  * [11] W. Kautz and R. Singleton, “Nonrandom binary superimposed codes,” IEEE Transactions on Information Theory, vol. 10, no. 4, pp. 363–377, 1964.
  * [12] E. Porat and A. Rothschild, “Explicit nonadaptive combinatorial group testing schemes,” IEEE Transactions on Information Theory, vol. 57, no. 12, pp. 7982–7989, 2011.
  * [13] P. Indyk, H. Q. Ngo, and A. Rudra, “Efficiently decodable non-adaptive group testing,” in Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1126–1142, Society for Industrial and Applied Mathematics, 2010.
  * [14] A. Mazumdar, “Nonadaptive group testing with random set of defectives via constant-weight codes,” arXiv preprint arXiv:1503.03597, 2015.
  * [15] K. Lee, R. Pedarsani, and K. Ramchandran, “Saffron: A fast, efficient, and robust framework for group testing based on sparse-graph codes,” arXiv preprint arXiv:1508.04485, 2015.
  * [16] T. Richardson and R. Urbanke, Modern coding theory.  Cambridge University Press, 2008.
  * [17] X. Li, S. Pawar, and K. Ramchandran, “Sub-linear time compressed sensing using sparse-graph codes,” in Proc. IEEE Int. Symp. Information Theory, pp. 1645–1649, 2015.
  * [18] S. Kumar, A. J. Young, N. Macris, and H. D. Pfister, “Threshold saturation for spatially coupled ldpc and ldgm codes on bms channels,” IEEE Trans. Inf. Theory, vol. 60, no. 12, pp. 7389–7415, 2014.
  * [19] S. Kudekar, T. Richardson, and R. L. Urbanke, “Spatially coupled ensembles universally achieve capacity under belief propagation,” IEEE Trans. Inf. Theory, vol. 59, no. 12, pp. 7761–7813, 2013.