# A Mutation-based Text Generation for Adversarial Machine Learning
Applications

Jesus Guerrero
Department of Computing and Cyber Security
Texas A&M University - San Antonio
San Antonio, TX 78224
<EMAIL_ADDRESS>
&Gongbo Liang
Department of Computing and Cyber Security
Texas A&M University - San Antonio
San Antonio, TX 78224
<EMAIL_ADDRESS>
&Izzat Alsmadi
Department of Computing and Cyber Security
Texas A&M University - San Antonio
San Antonio, TX 78224
<EMAIL_ADDRESS>

###### Abstract

Many natural language related applications involve text generation, created by
humans or machines. While in many of those applications machines support
humans, yet in few others, (e.g. adversarial machine learning, social bots and
trolls) machines try to impersonate humans. In this scope, we proposed and
evaluated several mutation-based text generation approaches. Unlike machine-
based generated text, mutation-based generated text needs human text samples
as inputs. We showed examples of mutation operators but this work can be
extended in many aspects such as proposing new text-based mutation operators
based on the nature of the application.

##  1 Introduction

Currently, text generation is widely used in Machine Learning (ML)-based or
Artificial Intelligence (AI)-based natural language applications such as
language to language translation, document summary, headline or abstract
generation. Those applications can be classified into different categories. In
one classification, they can be divided into short versus long text generation
applications. Short text generation applications include examples such as
predicting next word or statement, image caption generation, short language
translation, and documents summarization. Long text generation applications
include long text story completion, review generation, language translation,
poetry generation, and question answering. Large language models such as open
AI chat GPT-1,2 and 3 can be used to masquerade humans in many of those short
and long text generation applications. Unlike all previous applications where
ML or AI-based text generation exists to support humans and their
applications, in online social networks (OSN) such as Twitter and Facebook,
text generation is used to fool and influence humans and public opinions
through masquerading machine-generated texts as genuinely generated by humans.
Social bots and trolls in OSNs are accounts that impersonate humans. They are
controlled by ML or AI algorithms. ML algorithms are used to auto generate
text in those bot/troll accounts.

As mentioned earlier, ML-based text generation can be used for non-malicious
and malicious applications. Our focus in this paper is in malicious
applications. There are several malicious ML-based approaches to text
generation that can be observed in literature such as:

  * •

Classical (e.g. professor/teacher forcing recurrent neural network, RNN): It
aims to align generative behavior as closely as possible with teacher-forced
behavior, [1].

  * •

Conventional (e.g. based on hidden Markov models ([2]), method of moments
(MoM), [3], Restricted Boltzmann machine (RBM), [4] ).

  * •

Cooperative training, (e.g. [5], [6]).

  * •

Reinforcement based and Reinforcement free approaches (e.g. RankGAN, [7],
MaliGAN, [8], FMGAN, [9], and GSGAN, [10]).

In one classification to adversarial machine learning (AML) attacks, those
attacks can be divided based on at which machine learning stage the attack is
occurring (e.g. (1) learning/training stage, versus (2) testing stage).

###  1.1 Poisoning attacks: AML attacks on the learning stage: Manipulating
the training data

Attackers can deliberately influence the training dataset to manipulate the
results of a predictive model. A poisoning attack adds poisoned instances to
the training set and introduces new errors into the model. If we consider one
ML application, spam detection, filter of spam messages will be trained with
adversary instances to incorrectly classify the spam messages as good messages
leading to compromising of system’s integrity. Alternatively, the Spam
messages’ classifier will be trained inappropriately to block the genuine
messages thereby compromising system’s availability, [11], [12], [13], [14],
[15], [16], [17].

###  1.2 Evasion attacks: AML attacks on the testing stage: Manipulating the
testing data

In this attack, attackers try to evade the detection system by manipulating
the testing data, resulting in a wrong model classification. The core of
adversarial evasion attack is that when an attacker can fool a classifier to
think that a malicious input is actually benign, they can render a machine
learning-based malware detector or intrusion detector ineffective, [18], [19],
[20], [21]. [22]

Our mutation-based approach in this paper can fall under the first category of
the last classification (i.e. poisoning attacks). A mutation instance is a
data instance or object that is created from an original genuine instance with
a slight change. Such changes on machine learning stage can reduce accuracy of
classification algorithms through generating fake instances that are very
close to genuine instances. Mutation changes are typically introduced to
simulate actual real-world faults or mistakes. There are several scenarios to
implement our mutation-based AML:

  * •

Two class labels (Human/Mutation text): Human generated text versus mutation
generated text. Such experiments will test classifiers sensitivity to changes
injected by mutations in comparison with original genuine text.

  * •

Two class labels (Human/Adversarial, mutation instances are added to
adversarial instances

  * •

Two class labels (Human/Adversarial, mutation instances are added to Human
instances

  * •

Three class labels (Human/Mutation/Adversarial instances).

In this paper, we will propose and evaluate mutation operators within the
first category and leave investigating other categories in future papers.

The rest of the paper is organized as follows. Section 2 provides a summary of
related research. Our paper goals and approaches are introduced in 3. Section
4 covers the experiments we performed to evaluate our proposed mutation
operators. We have then a separate section, section 5 to compare with close
contributions. Finally, Section 6 provides some concluding remarks as well as
future extensions or directions.

##  2 Related Works

Machine learning NLP-based classifiers can be influenced by words misspelling
and all forms of adversarial text perturbations.

Literature survey indicated an increasing trend in using pre-trained models in
machine learning. Word/sentence embedding models and transformers are examples
of those pre-trained models. Adversarial models may utilize same or similar
pre-trained models as well. In another trend related to text generation
models, literature showed effort to develop universal text perturbations to be
used in both black and white-box attack settings, [23]. The literature on
adversarial text analysis is quite rich (e.g. see [24]). Our focus is in a
selection of those papers on adversarial text generation relevant to poisoning
attacks in general or mutation-based approaches in particular.

Word swapping (of semantically equivalent words) attack, [25] is similar to
one example of our mutation operators where one word is swapped from original
to mutation instances.
In [25],
[20] and [26], words are swapped based on genetic algorithms. Genetic
algorithms typically include 5 tasks in which mutation is one of them (Initial
population, Fitness function, Selection, Crossover, and Mutation). As
alternatives to genetic algorithms, word swapping attacks are also implemented
using (1) neural machine translation in , [27], (2) swarm optimization-based
search algorithm, [26]. In [25], mutation instances are used to fool a
sentiment analysis classifier.

Words substitution can be also role-based lexical substitutions, [28], or
entity-based text perturbation, [29].

In [30] authors classified intentional and unintentional adversarial text
perturbation into ten types, shown in Table 1.

Perturbation Type | Defense | Example | Definition
---|---|---|---
Combined Unicode | ACD |  | P.l.e.a.s.e.l.i.k.e.a.n.d.
---
s.h.a.r.e
| Insert a Unicode character between
---
each original character.
Fake punctuation | CW2V |  | Pleas.e lik,e abd shar!e the
---
v!deo
| Randomly add zero or more punc-
---
tuation marks between characters.
Neighboring key | CW2V |  | Plwase lime and sharr the
---
vvideo
| Replace character with keyboard-
---
adjacent characters.
Random spaces | CW2V |  | Pl ease lik e and sha re th e
---
video
| Randomly insert zero or more
---
spaces between characters.
Replace Unicode | UC |  | Pleãse lîke and sharê the
---
video
| Replace characters with Unicode
---
look-alikes
Space separation | ACD | Please l i k e and s h a r e | Place spaces between characters.
Tandem character obfuscation | UC |  | PLE/\SE LIKE /\ND
---
SH/\RE
| Replace individual characters with
---
characters that together look original
Transposition | CW2V | Please like adn sahre | Swap adjacent characters
Vowel repetition and deletion | CW2V | Pls likee nd sharee | Repeat or delete vowels.
Zero-width space separation | ACD |  Please like and share the video |  | Place zero-width spaces (Unicode
---
character 200c) between characters

Table 1: Adversarial text perturbations, [30]

As we mentioned earlier, this work is closely related to AML poisoning
attacks, [11], [12], [13], [14], [15], [16], [17].
It is also related to AML text perturbations, [31], [32], [33], and [34].

##  3 Goals and Approaches

According to a previous paper [35], a typical RoBERTa-based classifier
mislabels synthetic text to human by very basic differences such as changing
’a’s to alpha or ’e’s to epsilon. This vulnerability can be used to trick
detectors of synthetic text either intentionally or accidentally.

To compare synthetic text detectors sensitivity to mistakes or changes to
human text we can break up these mutations into operators with the goal of
supporting the creation of more generalized synthetic text detectors. Here,
these operators will be introduced and be used to fine-tune RoBERTa’s pre-
trained model to detect mutations, such as the first scenario mentioned
earlier, section 1.2.

###  3.1 Approach: Use a finite set of operators for research customization

We introduce some examples of mutation operators to implement are in Table 2.
These are more advanced can be used for attacking a detector on a more
granular level. For our research here however, we will be using more basic
mutation operators such as these:

Mutation Operator | Example | Definition
---|---|---
Randomization |  | Plz sh$\alpha$r and hate
---
film
| Use all below mutation
---
operators
Misspelling words |  | Plz sharr and like the
---
vid
Misspell a few words
Deleting articles |  | Please share and like
---
video
| Delete a few articles,
---
including starting ones
| Random word with
---
random word
| Please roar and tree
---
video
| Replace a random word
---
with another random word
Synonym replacement |  | Please disseminate and
---
prefer the video
| Replace a word with its
---
synonym
Antonym replacement |  | Please hide and hate
---
the video
| Replace a word with its
---
antonym
Replace ”a”, ”e” |  | Please like $\alpha$nd share
---
the video
| Replace some a’s and e’s
---
with epsilon & alpha

Table 2: Experimental mutation operators

These 7 operators can replicate simple mistakes and changes which can happen
to human written text, including the 2 operators used in previous cited works.
These were chosen for their ease of implementation and usage in previous
research. We will leave more advanced and numerous operators for future
papers.

As for the implementation, most of these operators use word maps which iterate
through each string replacing the words with the intended character, word
insertion or deletion. Punctuation and excess special characters are removed
for simplicity. Though there is different methods for the different mutation
operators.

The random word operator is in fact a list of random words. Arbitrary words
are chosen and replaced with a random word from the same list. Limits to the
number of mutations should be added to limit the operator from completely
fuzzing the string as well. The code from our GitHub,
https://github.com/JesseGuerrero/Mutation-Based-Text-Detection has some
written operators which can be viewed as examples.

In our implementation word maps are limited to 3000 of the most common words,
synonyms and antonyms. These words can be pulled from any API service such as
RapidAPI to get lists of words, synonyms, adverbs, verbs, etc.

###  3.2 Approach: Test mutations by Evasion attacks on neural network
detectors

We will be testing these 7 operators against RoBERTa pre-trained models. Of
these 7 operators we want to test how they will affect a previously researched
synthetic text detector, how a fine-tuned mutation text detector will be
affected and as well as the differences between the different mutation
operators. Lastly we want to see how shorter text affects these results. More
details on the next section, 4.

##  4 Experiments and Analysis

With these mutations, we can introduce mutation detection with a classic
binary RoBERTa classifier. This part of the experiment is the extension
portion of the previous author’s work mentioned before with an actual solution
to the vulnerabilities in that paper.

###  4.1 Experiment methodology

We used an existing RoBERTa classifier which is meant to classify synthetic
and human generated text to test how it would classify mutated text. It is
still the pre-trained binary model, however it is being retrained to detect
mutation rather than synthetic text.

The data set used was the full COCO images data set where hand written
captions are placed for each image. A total of 5 captions are human created
per image. The captions were parsed into a re-usable format and were used to
train the human portions of the model.

Across the training, testing and validation sets there were over 700,000 human
texts used to train the model. Two models were made from this data set. The
first was based on individual captions. The second was based on these 5
captions combined per unique image name for calling via a map.

Six operators were used as mutations for this classifier. They are; (1)
replacing synonyms, (2) antonyms, (3) random words, (4) removing articles, (5)
replacing a with alpha and e with epsilon, and lastly, (6) the most common
misspellings.

The training data was duplicated for the mutation data sets. Over 700,000
texts were used for training and the same texts were re-used for mutations.
This meant for individual captions there were over 1.4 million text instances
with both mutation and human labels. For combined captions there were 1/5 of
the total instances.

The data sets were selected as they were already labelled from COCO dataset.
The training set went to training, the validation set went to validation and
testing to testing. For training the mutation label, the mutation operators
were used at run-time.

The operator was randomly chosen at run-time with a simple random function
among 6 operators. Each operator was used so the classifier can learn to
detect all 6 of these mutation types in one classifier.

So far as testing is concerned, the same testing data set from COCO was re-
used with an operator manipulating a whole set. A total of 7 testing data sets
were created for each of the 6 operators and a seventh randomized data set,
like the mutations at run-time. This formed our metrics of how accurately the
model can correctly label each instance of the mutation data sets as mutations
and how accurately the model can label human text. In a total 8 operators, 1
human and a seventh randomizing the first six mutations.

###  4.2 Preliminary Results

If we were to apply these operators to the previously researched synthetic
text we should get poor results for detecting mutated text. Given text derived
from human text, though just modified, is still synthetic, we can see that
mutation poses a vulnerability to detecting machine and human generated texts.
Here are the results:

Operator Type | Accuracy
---|---
None |  $\sim$88.80%(1000 samples)
Randomized |  $\sim$01.00%(1000 samples)
Replace Alpha, Epsilon |  $\sim$01.01%(1000 samples)
Misspelling words |  $\sim$00.00%(1000 samples)
Delete articles |  $\sim$01.60%(1000 samples)
Synonym replacement |  $\sim$00.00%(1000 samples)
Replace random word |  $\sim$07.79%(1000 samples)
Antonym replacement |  $\sim$09.89%(1000 samples)
Table 3: Preliminary Results

As we can see from 1000 samples the accuracy is quite poor when modifying the
text. The original detector without mutations had a recall of over 97%
detection of synthetic and human text in-distribution. For our research
outside of the paper we have an out of distribution pure human text data set
as 88% accurate as the 1st row in the table.

This means the detector is quite good at classifying human text out of
distribution and is even good at detecting in-distribution synthetic text. The
model does those things above human distinction which in the past was around
54% accurate. Our issue from our modeling is mutation from which the model
does not perform well.

###  4.3 Experiments results & analysis

So far as the first run through with individual captions, the results were
pretty good. A total of 2,490 texts were tested for the detector from the
testing data set. In total overall the detector accuracy was about 91% and
each epoch took 13 hours for a total of 4 epochs or 52 hours total.

Operator Type | Accuracy
---|---
None |  $\sim$71.48%(2490)
Randomized |  $\sim$99.83%(2490)
Replace alpha, epsilon |  $\sim$99.95%(2490)
Misspelling words |  $\sim$99.95%(2490)
Delete articles |  $\sim$59.87%(2490)
Synonym replacement |  $\sim$99.91%(2490)
Replace random word |  $\sim$100%(2490)
Antonym replacement |  $\sim$99.03%(2490)
Table 4: Individual captions, short language modeling

The most inaccurate operator overall was always the ”delete articles
operator”. This can be due to some semantic issues or just the difficulty of
detecting what is _not_ there rather than what _is there_ to a RoBERTa
classifier. For this first run, the other operators ranged from 59% accurate
to 100% accurate, with human detection being 71%.

For the second run the captions for text chunks were combined per image. This
meant all 5 captions were now one text and were fed to the training model.
This means 1/5 th of the instances but more per text. The results were a
slightly lower; total overall detector accuracy of 88% with 2490 texts being
tested.

The epochs took about 2 hours each this way as well. A total of 10 epochs or
20 hours were used to finish the model training. Same as before, the delete
articles operator was the weakest mutator and was in fact even weaker the
second time.

Operator Type | Accuracy
---|---
None |  $\sim$93.65%(2490)
Randomized |  $\sim$98.96%(2490)
Replace alpha, epsilon |  $\sim$99.92%(2490)
Misspelling words |  $\sim$99.80%(2490)
Delete articles |  $\sim$25.42%(2490)
Synonym replacement |  $\sim$99.76%(2490)
Replace random word |  $\sim$98.43%(2490)
Antonym replacement |  $\sim$92.37%(2490)
Table 5: Combined captions, longer language modeling

Besides the weakest operators, the other operators were all above 95%, much
better than the original neural network. If we were to remove the lowest
performing operator we would in fact have 95% accuracy for the 1st run and 97%
accuracy for the 2nd. This means in reality the combined text may be the
better approach to train.

###  4.4 Experiment: Models issues and weaknesses

The main issue of the evaluated models is possible a bias issue. It seems that
models work mostly for semi in-distribution data sets. So accuracy is altered
quite a bit by outside data sets. Both the individually captioned model and
the grouped model were tested in an out of distribution data set. The
individually captioned data set was 2.2% accurate for human detection and 100%
accurate for Alpha/Epsilon mutation, while the grouped captioned data set was
55.7% accurate for human detection and 100% for Alpha/Epsilon mutation. The
issue appears to be the out of distribution set may have had vocabulary that
didn’t exist in distribution and the detector defaults to the mutation label.
Still in this sense, the longer the text-set the better is the performance.

In the future we can use this work flow with more diverse training data sets
to generalize models to out of distribution and use these models to prevent
simple mutation from fooling binary detectors. Lastly, the mutation operator
”delete articles” seems like a great way to fool the classifier into
mislabeling mutated text.

##  5 A Comparison Study

###  5.1 Machine Text Generation

Machine text generation is a field of study in Natural Language Processing
(NLP) that combines computational linguistics and artificial intelligence that
has progressed significantly in recent years. Neural network approaches are
widely used for this task and keep dominant in the field. The state-of-the-art
methods may include Transformers [36], BERT [37], GPT-3 [38], RoBERTa [39],
etc. The models are trained on a large amount of text data. For example, the
GPT-2 model was trained on text scrapped from eight million web pages [40],
and is able to generate human-like text. Due to the high text generation
performance, such methods are very popular on tasks, such as image caption
generation, text summarization, machine translation, moving script-writing,
and poetry composition. However, the output of such methods is often open-
ended.

Through this work, we propose a mutation-based text generation method that can
be distinguished from the existing text generation method fundamentally.
Unlike the neural network based methods, the mutation-based method generates
output based on the given text under a given condition. The text is generated
in a tightly controlled environment, and the output is closed-ended. The well-
controlled environment makes the output of the mutation-based method suitable
for serious security test tasks, such as machine learning model vulnerability
tests and SQL injection defense and detection.

Given a text corpus (e.g., a sentence or a paragraph), $\mathcal{T}$, which
contains an ordered set of words, $\mathcal{W}=\\{w_{1},w_{2},...,w_{n}\\}$,
and an ordered set of punctuation, $\mathcal{P}=\\{p_{1},p_{2},...,p_{m}\\}$,
a mutation operator, $\mu(\cdot)$ is used to generate the mutation-based text.
For instance, given a character-level mutation operator, $\mu_{c}(\cdot)$:

$\mathcal{W}^{\prime}=\mu_{c}(w_{i},\rho,\sigma),$ (1)

where $\mathcal{W}^{\prime}$ is the output of $\mu_{c}(\cdot)$, which replaces
the letter $\rho$ in $w_{i}$ ($w_{i}\in\mathcal{W}$) with a mutation $\sigma$.
Then, the final output of $\mathcal{T}$ is
$\mathcal{T}^{\prime}=\langle\mathcal{W}^{\prime},\mathcal{P}\rangle$. For
instance, assume $\mathcal{T}=$ "Text generation is interesting!",
$\mathcal{W}=\\{\texttt{Text},\texttt{generation},\texttt{is},\texttt{interesting}\\}$,
and $\mathcal{P}=\\{\texttt{!}\\}$, $w_{i}=\texttt{generation}$, and a
character-level mutation operator $\mu_{u}(\cdot)$, where $\rho=\texttt{a}$
and $\sigma=\alpha$ (the Greek letter alpha). Then, the output text corpus,
$\mathcal{T}^{\prime}$ is generated as:

$\begin{split}\mathcal{T}^{\prime}&=\langle\mathcal{W}^{\prime},\mathcal{P}\rangle\\\
&=\langle\mu_{c}(w_{i},\rho,\sigma),\mathcal{P}\rangle\\\
&=\langle\mu_{c}(\texttt{generation},\texttt{a},\alpha),\mathcal{P}\rangle\\\
&=\texttt{Text gener}\alpha\texttt{tion is interesting!}\end{split}$ (2)

###  5.2 Mutation Testing in the Language Domain

The proposed mutation-based text generation is inspired by the advances in
mutation analysis in software testing and the idea of ”broiling frog syndrome”
The well-controlled and close-ended environment makes generating precise text
output possible. By using the proposed tool, researchers could test a language
model by changing the input slightly and step-by-step.

Charm [24] is a chat-bot testing tool closely related to our mutation-based
text generator that extended Botium [41]—a popular framework for chat-bot
testing—by integrating eight mutation operators. Though both Charm and ours
use mutation operators, Charm is proposed as an extension to Botium and relies
on Botium to work. In addition, Charm only works for chat-bot testing.

Unlike Charm, ours is a general-purpose language generation method, which is
designed to work alone. Our method can be used to analyze any type of language
models that accept a sequence of text as input. In addition, the users are not
limited by the pre-defined mutation operators. Our proposed mutation-based
text generator is a general framework. The users could easily design their own
mutation operators for their specific tasks within our framework.

##  6 Discussions, Conclusions and Future Directions

Automatic text generation techniques are adopted into various domains, from
question-answering to AI-driven education. Due to the progress of neural
network (NN) techniques, NN-based approaches dominate the field. Though
advanced techniques may be applied to control text generation direction, the
text is still generated in a widely open-ended fashion. For instance, a NN-
based approach can generate a greeting message to greet a specific person.
However, it is hard to control the exact wording used in the message. Such
open-ended text generation might work fine for content generation tasks.
However, due to lack of precise control, using open-ended text generation
methods to systematically evaluate flaws in language analysis models may be
non-trivial.

Unlike the existing language models, our proposed mutation-based text-
generation framework provides a tightly controlled environment for text
generation that extends text-generation techniques to the field of cyber
security (i.e., flaws evaluation for language analysis models). The output of
our framework can be used to systematically evaluate any machine learning
models or software systems that use a sequence of text as input, such as SQL
injection detection [42] and software debugging [43]. Researchers may also
design their own mutation operators under our framework.

We demonstrated the proposed text-generation framework using the RoBERTa-based
detector that is pre-trained for separating human-written text from synthetic
ones. Our experiments showed that the RoBERTa-based detector has a significant
flaw. As a detection method, it is extremely vulnerable to simple adversarial
attacks, such as replacing the English letter ”a” with the Greek letter
”$\alpha$” or removing the articles—a, an, the—from a sentence. We also
demonstrated that simply including the adversarial samples (i.e., the mutation
texts) in the fine-tuning stage of the classifier would significantly improve
the model robustness on such types of attack. However, we believe that this
issue should be better addressed on the feature level since any changes at the
text level will lead to changes in the tokenization stage that will eventually
lead to a different embedding vector being fed into the classification
network. Thus, one future direction of this work is reducing the distance
between the original and mutation samples in the feature space. Some
potentially useful methods might include using contrastive learning and
siamese network [44, 45] as well as dynamic feature alignment [46, 47].

Besides improving the robustness of the RoBERTa-based detector, we plan to
continue to work on the development of the proposed mutation-based text
generation framework. Currently, the framework only works in a two-step
testing scenario. Users need to use the framework to generate the testing
cases and feed the testing cases into the downstream model in separate steps.
We plan to release a library that can be directly imported into any downstream
applications. Tools for easily creating and editing mutation operators will
also be created. In addition, a graphical user interface may also be
developed.

In conclusion, we propose a general-purpose, mutation-based text generation
framework that produces close-ended, precise text. The output of our framework
can be used in various downstream applications that take text sequences as
input, providing a systematic way to evaluate the robustness of such models.
We believe the proposed framework offers a new direction to systematically
evaluate language models that will be very useful to those who are seeking
insightful analysis of such models.

## References

  * Lamb et al. [2016] Alex M Lamb, Anirudh Goyal ALIAS PARTH GOYAL, Ying Zhang, Saizheng Zhang, Aaron C Courville, and Yoshua Bengio.  Professor forcing: A new algorithm for training recurrent networks.  _Advances in neural information processing systems_ , 29, 2016.
  * Jing [2002] Hongyan Jing.  Using hidden markov modeling to decompose human-written summaries.  _Computational linguistics_ , 28(4):527–543, 2002\.
  * Jones [1969] DS Jones.  Field computation by moment methods, 1969.
  * Holyoak [1987] Keith J Holyoak.  Parallel distributed processing: explorations in the microstructure of cognition.  _Science_ , 236:992–997, 1987.
  * Yin et al. [2020] Haiyan Yin, Dingcheng Li, Xu Li, and Ping Li.  Meta-cotgan: A meta cooperative training paradigm for improving adversarial text generation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 9466–9473, 2020.
  * Lu et al. [2019] Sidi Lu, Lantao Yu, Siyuan Feng, Yaoming Zhu, and Weinan Zhang.  Cot: Cooperative training for generative modeling of discrete data.  In _International Conference on Machine Learning_ , pages 4164–4172. PMLR, 2019.
  * Lin et al. [2017] Kevin Lin, Dianqi Li, Xiaodong He, Zhengyou Zhang, and Ming-Ting Sun.  Adversarial ranking for language generation.  _Advances in neural information processing systems_ , 30, 2017.
  * Che et al. [2017] Tong Che, Yanran Li, Ruixiang Zhang, R Devon Hjelm, Wenjie Li, Yangqiu Song, and Yoshua Bengio.  Maximum-likelihood augmented discrete generative adversarial networks.  _arXiv preprint arXiv:1702.07983_ , 2017.
  * Chen et al. [2018] Liqun Chen, Shuyang Dai, Chenyang Tao, Haichao Zhang, Zhe Gan, Dinghan Shen, Yizhe Zhang, Guoyin Wang, Ruiyi Zhang, and Lawrence Carin.  Adversarial text generation via feature-mover’s distance.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Kusner and Hernández-Lobato [2016] Matt J Kusner and José Miguel Hernández-Lobato.  Gans for sequences of discrete elements with the gumbel-softmax distribution.  _arXiv preprint arXiv:1611.04051_ , 2016.
  * Newsome et al. [2006] James Newsome, Brad Karp, and Dawn Song.  Paragraph: Thwarting signature learning by training maliciously.  In _International Workshop on Recent Advances in Intrusion Detection_ , pages 81–105. Springer, 2006.
  * Perdisci et al. [2006] Roberto Perdisci, David Dagon, Wenke Lee, Prahlad Fogla, and Monirul Sharif.  Misleading worm signature generators using deliberate noise injection.  In _2006 IEEE Symposium on Security and Privacy (S &P’06)_, pages 15–pp. IEEE, 2006.
  * Nelson et al. [2008] Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles Sutton, J Doug Tygar, and Kai Xia.  Exploiting machine learning to subvert your spam filter.  _LEET_ , 8(1):9, 2008.
  * Rubinstein et al. [2009] Benjamin IP Rubinstein, Blaine Nelson, Ling Huang, Anthony D Joseph, Shing-hon Lau, Satish Rao, Nina Taft, and J Doug Tygar.  Antidote: understanding and defending against poisoning of anomaly detectors.  In _Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement_ , pages 1–14, 2009.
  * Barreno et al. [2010] Marco Barreno, Blaine Nelson, Anthony D Joseph, and J Doug Tygar.  The security of machine learning.  _Machine Learning_ , 81(2):121–148, 2010.
  * Biggio et al. [2012] Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning attacks against support vector machines.  _arXiv preprint arXiv:1206.6389_ , 2012.
  * Newell et al. [2014] Andrew Newell, Rahul Potharaju, Luojie Xiang, and Cristina Nita-Rotaru.  On the practicality of integrity attacks on document-level sentiment analysis.  In _Proceedings of the 2014 Workshop on Artificial Intelligent and Security Workshop_ , pages 83–93, 2014.
  * Russu et al. [2016] Paolo Russu, Ambra Demontis, Battista Biggio, Giorgio Fumera, and Fabio Roli.  Secure kernel machines against evasion attacks.  In _Proceedings of the 2016 ACM workshop on artificial intelligence and security_ , pages 59–69, 2016.
  * Zhang et al. [2020] Fuyong Zhang, Yi Wang, Shigang Liu, and Hua Wang.  Decision-based evasion attacks on tree ensemble classifiers.  _World Wide Web_ , 23(5):2957–2977, 2020.
  * Sayghe et al. [2020] Ali Sayghe, Junbo Zhao, and Charalambos Konstantinou.  Evasion attacks with adversarial deep learning against power system state estimation.  In _2020 IEEE Power & Energy Society General Meeting (PESGM)_, pages 1–5. IEEE, 2020.
  * Shu et al. [2022] Rui Shu, Tianpei Xia, Laurie Williams, and Tim Menzies.  Omni: automated ensemble with unexpected models against adversarial evasion attack.  _Empirical Software Engineering_ , 27(1):1–32, 2022.
  * Chernikova and Oprea [2022] Alesia Chernikova and Alina Oprea.  Fence: Feasible evasion attacks on neural networks in constrained environments.  _ACM Transactions on Privacy and Security_ , 25(4):1–34, 2022.
  * Alsmadi et al. [2022] Izzat Alsmadi, Nura Aljaafari, Mahmoud Nazzal, Shadan AlHamed, Ahmad Sawalmeh, Conrado P Vizcarra, Abdallah Khreishah, Muhammad Anan, Abdulelah Algosaibi, Mohammed Alnaeem, et al.  Adversarial machine learning in text processing: A literature survey.  _IEEE Access_ , 2022.
  * Bravo-Santos et al. [2020] Sergio Bravo-Santos, Esther Guerra, and Juan de Lara.  Testing chatbots with charm.  In _International Conference on the Quality of Information and Communications Technology_ , pages 426–438. Springer, 2020.
  * Alzantot et al. [2018] Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani Srivastava, and Kai-Wei Chang.  Generating natural language adversarial examples.  _arXiv preprint arXiv:1804.07998_ , 2018.
  * Shi et al. [2022] Dingmeng Shi, Zhaocheng Ge, and Tengfei Zhao.  Word-level textual adversarial attacking based on genetic algorithm.  In _Third International Conference on Computer Communication and Network Security (CCNS 2022)_ , volume 12453, pages 272–276. SPIE, 2022.
  * Ribeiro et al. [2018] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Semantically equivalent adversarial rules for debugging nlp models.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_ , 2018.
  * Iyyer et al. [2018] Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer.  Adversarial example generation with syntactically controlled paraphrase networks.  _arXiv preprint arXiv:1804.06059_ , 2018.
  * Liu and Chen [2022] Zhengyuan Liu and Nancy Chen.  Entity-based de-noising modeling for controllable dialogue summarization.  In _Proceedings of the 23rd Annual Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 407–418, 2022.
  * Bhalerao et al. [2022] Rasika Bhalerao, Mohammad Al-Rubaie, Anand Bhaskar, and Igor Markov.  Data-driven mitigation of adversarial text perturbation.  _arXiv preprint arXiv:2202.09483_ , 2022.
  * Vijayaraghavan and Roy [2019] Prashanth Vijayaraghavan and Deb Roy.  Generating black-box adversarial examples for text classifiers using a deep reinforced model.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 711–726. Springer, 2019.
  * Eger et al. [2019] Steffen Eger, Gözde Gül Şahin, Andreas Rücklé, Ji-Ung Lee, Claudia Schulz, Mohsen Mesgar, Krishnkant Swarnkar, Edwin Simpson, and Iryna Gurevych.  Text processing like humans do: Visually attacking and shielding nlp systems.  _arXiv preprint arXiv:1903.11508_ , 2019.
  * Gao et al. [2018] Ji Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi.  Black-box generation of adversarial text sequences to evade deep learning classifiers.  In _2018 IEEE Security and Privacy Workshops (SPW)_ , pages 50–56. IEEE, 2018.
  * Li et al. [2018] Jinfeng Li, Shouling Ji, Tianyu Du, Bo Li, and Ting Wang.  Textbugger: Generating adversarial text against real-world applications.  _arXiv preprint arXiv:1812.05271_ , 2018.
  * Wolff and Wolff [2020] Max Wolff and Stuart Wolff.  Attacking neural text detectors.  2 2020.  URL http://arxiv.org/abs/2002.11768.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Liu et al. [2019] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Jin et al. [2020] Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits.  Is bert really robust? a strong baseline for natural language attack on text classification and entailment.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 8018–8025, 2020.
  * Hlaing and Khaing [2020] Zar Chi Su Su Hlaing and Myo Khaing.  A detection and prevention technique on sql injection attacks.  In _2020 IEEE Conference on Computer Applications (ICCA)_ , pages 1–6. IEEE, 2020.
  * Zhao et al. [2022] Yu Zhao, Ting Su, Yang Liu, Wei Zheng, Xiaoxue Wu, Ramakanth Kavuluru, William GJ Halfond, and Tingting Yu.  Recdroid+: Automated end-to-end crash reproduction from bug reports for android apps.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , 31(3):1–33, 2022.
  * Koch et al. [2015] Gregory Koch, Richard Zemel, Ruslan Salakhutdinov, et al.  Siamese neural networks for one-shot image recognition.  In _ICML deep learning workshop_ , volume 2, page 0. Lille, 2015.
  * Liang et al. [2021] Gongbo Liang, Connor Greenwell, Yu Zhang, Xin Xing, Xiaoqin Wang, Ramakanth Kavuluru, and Nathan Jacobs.  Contrastive cross-modal pre-training: A general strategy for small sample medical imaging.  _IEEE Journal of Biomedical and Health Informatics_ , 26(4):1640–1649, 2021.
  * Zhang et al. [2022] Yu Zhang, Gongbo Liang, and Nathan Jacobs.  Dynamic feature alignment for semi-supervised domain adaptation.  _British Machine Vision Conference (BMVC)_ , 2022.
  * Dong et al. [2020] Jiahua Dong, Yang Cong, Gan Sun, Yuyang Liu, and Xiaowei Xu.  Cscl: Critical semantic-consistent learning for unsupervised domain adaptation.  In _European Conference on Computer Vision_ , pages 745–762. Springer, 2020.


# Performance Bounds for LASSO under Multiplicative Noise: Applications to
Pooled RT-PCR Testing

Richeek Das<EMAIL_ADDRESS>Aaron Jerry Ninan<EMAIL_ADDRESS>Adithya Bhaskar<EMAIL_ADDRESS>Ajit Rajwade
<EMAIL_ADDRESS>
###### Abstract

Group/Pooled testing is a technique which involves testing $n$ samples for a
rare disease in an indirect manner: instead of individually testing each of
the $p$ samples, it involves creating $n<p$ pools and testing each pool, where
a pool consists of a mixture of small, equal portions of a subset of the $p$
samples. Group testing is known to save a large amount of testing time and
resources in a variety of application settings. There also exist good
theoretical guarantees for the recovery of the status of the $p$ samples from
results on $n$ pools, if certain conditions are satisfied. The popularity of
group testing for RT-PCR testing is also well-known. The noise in quantitative
RT-PCR is known to follow a multiplicative and data-dependent model, which
emerges from properties inherent to RT-PCR. In recent literature, the
corresponding linear systems for inference of the health status of $p$ samples
from results on $n$ pools, have been solved using the well-known Lasso
estimator and its variants [1], which have been widely used in the compressed
sensing literature. However, the Lasso has typically been used in additive
Gaussian noise settings. There is no existing literature which establishes
performance bounds for Lasso for the multiplicative noise model associated
with RT-PCR. After noting that a general technique proposed in [2] works well
for establishing performance bounds for Lasso in Poisson inverse problems, we
adapt it to handle sparse signal reconstruction from compressive measurements
with multiplicative noise, as would appear in pooled RT-PCR testing. In
particular, we present high probability performance bounds and data-dependent
weights for the Lasso and a weighted version of the Lasso under multiplicative
Gaussian Noise. We also show numerical results on simulated pooled RT-PCR data
to empirically validate our developed bounds.

###### keywords:

Compressed sensing, Performance Analysis and Bounds, Multiplicative Noise,
Group Testing, RT-PCR

††journal: Signal Processing

[label1]organization=Indian Institute of Technology Bombay,
addressline=Department of Computer Science and Engineering
[label3]organization=Indian Institute of Technology
Bombay,addressline=Department of Electrical Engineering

##  1 Introduction

The COVID-19 pandemic led to massive lockdowns worldwide, causing disruptions
in industry, education and the well-being of people. Symptoms of this virus
were often similar to those of the common cold, flu, etc. This, combined with
the highly infectious nature of COVID-19, made early detection of the virus in
individuals for subsequent isolation, one of the significant challenges faced
by testing laboratories.

RT-PCR (Reverse Transcription-Polymerase Chain Reaction) [3] is a highly
reliable method for detecting viruses, and was widely deployed during the
COVID-19 pandemic. It involves obtaining a sample from the nose or throat of a
person, chemically treating it to extract viral RNA (if present in the
sample), and then converting the RNA to DNA through a process called reverse
transcription. Short DNA fragments complementary to the viral DNA are added to
the sample, which is then passed through a DNA amplification process. The
presence of the virus is detected using fluorescent markers, and if the total
fluorescence exceeds a certain threshold, the sample is considered positive
for the virus. The number of cycles of amplification $C_{t}$ (cycle threshold)
required to exceed this threshold is reported. A larger viral load will
produce a larger amount of complementary DNA and thus produce the critical
level of fluorescence earlier on in the RT-PCR process, leading to a lower
$C_{t}$ value. Likewise, smaller viral loads are associated with higher
$C_{t}$ values.

However, the low prevalence rate of COVID-19 means that most test samples turn
out to be negative, leading to wastage of valuable resources, if every sample
has to be tested. In an effort to reduce the cost and burden of RT-PCR
testing, various algorithms have been proposed, that allow for the pooling of
samples in order to achieve the same or slightly lower diagnostic accuracy
with fewer tests [4]. One such algorithm is Tapestry, which was introduced in
[1], and which combines ideas from combinatorial group testing and compressed
sensing (CS). Other methods such as [5, 6] also use interesting ideas from
group testing (GT) and CS. Another approach, described in [7, 8], uses
additional side information such as family membership or via contact tracing
information. This additional information is shown to further improve the
accuracy of the detection algorithms. All these algorithms serve two purposes:
(i) To reduce the number of testing kits required per person (which were
scarce in many countries during COVID-19 surges), and (ii) To increase testing
throughput by parallelizing multiple pooled tests.

Simple two-round group testing schemes such as Dorfman testing [9] had already
been applied in the field by several research labs [10], [11] for COVID-19
testing. However Dorfman testing is a two-round procedure where the output of
the first round acts as input to the second round. This increases testing time
significantly, because the second round cannot begin before completion of the
first round, and because one round of RT-PCR takes about 3-4 hours to
complete. On the other hand, methods such as Tapestry [1] are non-adaptive and
work in a single round. This saves on testing time, which is very critical
during the peak of a pandemic. In fact, some recent research [12] argues that
testing time is even more important than accuracy at the peak of a pandemic.

Tapestry is based on principles of CS. CS [13] is a mathematical framework
that allows for the efficient recovery of sparse signals from a small number
of carefully chosen linear measurements. Let $\bm{x^{*}}\in\text{R}^{p}$ be a
signal with only $s\ll p$ non-zero elements at unknown indices. The signal
$\bm{x^{*}}$ is observed in an indirect manner via linear measurements of the
form $\bm{y}=\bm{Ax^{*}}+\bm{w}$ where $\bm{A}\in\text{R}^{n\times p},n\ll p$
is a so called sensing matrix with fewer rows than columns,
$\bm{y}\in\text{R}^{n}$ is a measurement vector, and $\bm{w}\in\text{R}^{n}$
is an additive noise vector. Using simple convex optimization procedures, it
has been shown that the sparse vector $\bm{x^{*}}$ can be recovered stably and
robustly from $\bm{y},\bm{A}$ provided two (related) conditions are met: (i)
The number of measurements should be at least $O(s\ln p)$, and (ii) The matrix
$\bm{A}$ should obey the property that its nullspace accommodates no signal
with $s$ or fewer than $s$ non-zero elements, barring the zero vector. CS has
found numerous applications in signal processing, image reconstruction, and
other fields and has been particularly useful for sparse linear inverse
problems, such as those encountered in pooled RT-PCR testing. Note that most
traditional GT algorithms (see [14] for a survey) treat both $\bm{y}$ and
$\bm{x^{*}}$ as binary. However, CS produces a distinct advantage over these
traditional GT algorithms: it allows us to determine _quantitative_
information such as viral load, over and above a mere binary indicator of
whether or not the sample is diseased [5, 1, 7, 8].

The well known Lasso estimator in statistics [15] and its variants are popular
methods for solving sparse linear inverse problems in CS. The estimator is
given as follows:

$\bm{\hat{x}}:=\textrm{argmin}_{\bm{x}}\|\bm{y}-\bm{Ax}\|^{2}+\lambda\|\bm{x}\|_{1},$
(1)

where $\lambda>0$ is a regularization parameter. Lasso has been used in group
testing, including the Tapestry algorithm [1]. Its variants such as the group
Lasso [16] are useful methods to exploit side information to enhance group
testing performance [7, 8]. There is a rich literature on theoretical
performance bounds for the Lasso under additive Gaussian [15, Chapter 11] and
Poisson noise [2, 17]. [2] also provides a novel analysis of a _weighted_
version of Lasso, deriving data-dependent weights and chalking out a
generalized framework for handling data-dependent noise, with emphasis on the
Poisson noise model which is widely used for optical imaging systems. However,
the nature of RT-PCR testing introduces multiplicative noise (as we shall see
in detail in Sec. 2.1), whose effective variance scales directly with the
values of the unknown vector $\bm{x^{*}}$. While the Lasso has been shown to
numerically perform well in this setting [1], its theoretical bounds for this
noise model have not been established in the literature to the best of our
knowledge. It is important to have a better understanding of the theoretical
performance guarantees of the Lasso under multiplicative noise to rigorously
justify the use of this estimator in a multiplicative noise setting such as
that encountered in pooled RT-PCR.

In this paper, we draw from a general technique proposed in [18] and adapt the
data-dependent performance bounds for Lasso in Poisson inverse problems as
presented in [2], to the case of multiplicative noise in the context of pooled
RT-PCR testing. We derive high-probability performance bounds, obtained via
data-dependent weights for Lasso and its weighted variant (details provided
later in this paper), assuming randomly generated Bernoulli pooling matrices.
We support our theory through numerical experiments.

In parallel to this work, our group has done other work [19] on the analysis
of the Lasso for multiplicative noise in compressive RT-PCR. This work may be
submitted for publication later, independent of the work presented in this
paper. There are two main differences between [19] and this work: (i) the
former does not explore a weighted version of Lasso, as we do here (see
Equation 7), and (ii) unlike [19], the work here considers a Taylor series
based expansion of the multiplicative noise model (see Eqns. 3 and 4).

##  2 Theory

###  2.1 Problem Formulation

In RT-PCR testing, a naso- or oro-pharyngeal swab is taken from a person being
tested. The mucus in the swab is mixed in a liquid medium and tested in an RT-
PCR machine. [20] surveys multiple group testing techniques in detail, where
they pool (mix) subsets of $p$ samples and test the $n$ pools
($\\#\text{pools}(n)<\\#\text{samples}(p)$) to save resources. Small, equal
portions of participating samples are used for creating any pool. Given a
negative pooled test, one can conclude that all contributing samples are non-
infected, as RT-PCR is known to be highly sensitive by design due to the DNA
amplification involved. In case some of the pooled tests are positive, we
would like to deduce which participants are infected without repeated rounds
of testing. This part is non-trivial.

More formally, we can state the computational problem as follows. Let
$\bm{x^{*}}\in\text{R}^{p}$ represent the vector of viral loads of the samples
collected from $p$ individuals (one per individual). All entries of
$\bm{x^{*}}$ are non-negative and $x_{i}=0$ would imply that the sample of the
$i$th individual is not infected. To model the low infection rate for
COVID-19, we consider $\bm{x^{*}}$ to be a sparse vector with very few
positive valued elements. The mixing of samples into groups (or pools) can be
modeled with the help of a binary mixing matrix $\bm{A}\in\\{0,1\\}^{n\times
p}$ (also called pooling matrix or sensing matrix), where $n<p$ and where
entry $A_{ij}$ is 1 if the sample from the $j$th person is included while
creating the $i$th pool and 0 otherwise. The resulting viral loads in pooled
samples will be given by $\bm{y}\in\text{R}^{n}$, where:

$y_{j}=\sum_{i=1}^{p}A_{ji}x^{*}_{i}=\bm{A^{j}}\bm{x^{*}},\,1\leq j\leq n.$
(2)

Here, $\bm{A^{j}}$ is the $j$th row of $\bm{A}$.

However, due to the stochasticity of the reaction, measurement error in the
PCR machine, and exponential growth of the number of molecules of viral cDNA
in all the pools, a multiplicative Gaussian noise model is used for $\bm{y}$.
We use the noise model derived in [1] for our analysis:

$y_{j}=\bm{A^{j}}\bm{x^{*}}(1+q_{a})^{w_{j}}.$ (3)

Here, $q_{a}\in(0,1)$ is the known fraction of viral cDNA that replicates in
each cycle (sometimes referred to as the amplification factor), and
$w_{j}\sim\mathcal{N}(0,\,\sigma^{2})$ is the sample of a random variable
which represents the difference between the true cycle time and
observed/recorded cycle time. Here $\sigma$ is the standard deviation of
$w_{j}$. Usually, the time difference is small, and hence we can assume
$\sigma<1$ (Fig.1 of Additional File 3 in [21]), as has also been done in [1,
7].

Several classes of binary pooling matrices have shown promising results when
applied to the problem of inferring $\bm{x^{*}}$ from $\bm{y},\bm{A}$, as
shown in [1]. This includes different types of deterministically generated
matrices. However, to simplify our analysis, we limit our study to the class
of random Bernoulli sensing matrices, where each element of the matrix is
drawn independently from the $\textrm{Bernoulli}(q)$ distribution for some
$q\in(0,1)$. That is, each entry $a_{ij}$ of matrix $\bm{A}$ is independently
0 with probability $1-q$ and 1 with probability $q$.

Our study is in the low variance regime, i.e. $\sigma<1$, which we would later
see appears to be an essential assumption for accurate or near-accurate
recovery of $\bm{x^{*}}$ from $\bm{y},\bm{A}$. This assumption is also
supported in practice by RT-PCR systems, since the variance of the cycle time
readings is very low as mentioned earlier. Additionally, this assumption
allows us to approximate the multiplicative Gaussian noise model by
linearizing Equation 3 using a first order Taylor series expansion, as also
mentioned in [7, Sec. VII]:

$y_{j}\approx\bm{A^{j}}\bm{x^{*}}+[\bm{A^{j}x^{*}}\ln(1+q_{a})]w_{j},\text{
where }w_{j}\sim\mathcal{N}(0,\sigma^{2}).$ (4)

Our target is to recover vector $\bm{x^{*}}$ using our pooled viral loads
$\bm{y}$ and the pooling matrix $\bm{A}$. Note that the approximation in the
above equation is tight since $\sigma<1$, all powers of $\ln(1+q_{a})$ are
less than 1 and due to division by factors such as $2!,3!$, etc. All this
makes the second-order or higher order terms of the Taylor series expansion
negligible in magnitude. The Taylor expansion of $y_{j}$ is as follows:

$y_{j}\approx\bm{A^{j}}\bm{x^{*}}\left(1+\ln(1+q_{a})w_{j}+\frac{1}{2}\ln^{2}(1+q_{a})w_{j}^{2}+\cdots\right)$
(5)

As $w_{j}\sim\mathcal{N}(0,\sigma^{2})$ and $\sigma<1$, we can ignore the
higher order terms of $w_{j}^{2}$, $w_{j}^{3}$, $\cdots$, and end up with
Equation 4. Ideally, this approximation is valid only with high probability.
But for simplicity, we treat it as exact.

The Taylor series expansion casts this model as a special case of additive
signal dependent noise. Note that the additive noise variance in this model
(see Equation 4) is proportional to the _square_ of the mean, unlike the case
of Poisson noise, where the noise variance is _equal_ to the mean. Along a
related vein, the work in [22] presents an interesting case where the noise in
the compressive measurements is linearly correlated with the signal, and many
applications including quantization noise are handled. However no theoretical
performance bounds are presented, and multiplicative noise is not considered.

###  2.2 Estimation methods

We consider two estimators in this work: the Lasso and the weighted Lasso
(referred to henceforth as WLasso), both for the case of multiplicative noise
in $\bm{y}$.

The Lasso estimator is presented here below:

$\bm{\hat{x}^{L}}=\operatorname*{argmin}_{\bm{x}\in\text{R}^{p}}\|\bm{y}-\bm{Ax}\|_{2}^{2}+\gamma\sum_{k=1}^{p}\beta|x_{k}|,$
(6)

where $\gamma>2$ is a constant and $\beta>0$ is a data-dependent scalar.

The WLasso estimator uses a possibly different weight for each element of
$\bm{x}$, as shown below:

$\bm{\hat{x}^{WL}}=\operatorname*{argmin}_{\bm{x}\in\text{R}^{p}}\|\bm{y}-\bm{Ax}\|_{2}^{2}+\gamma\sum_{k=1}^{p}\beta_{k}|x_{k}|,$
(7)

where $\gamma>2$ is a constant and $\beta_{k}>0$ is the $k$th data-dependent
scalar. The exact expressions of $\beta$ and $\beta_{k}$ depend on the
observed data. Deriving expressions for $\beta$ and $\beta_{k}$ forms the crux
of our work in this paper (albeit for modified forms of these estimators
presented later in Equation 16 and Equation 17).

Additionally, note that a logarithmic transformation on $\bm{y}$ will act as a
variance stabilization transform [23] for multiplicative noise, just as the
square-root transform acts a variance stabilizer for Poisson noise and has
shown great success in Poisson/Poisson-Gaussian inverse problems [24, 25],
tomography [26] and deblurring [27]. The associated estimator for our
multiplicative noise outlined in Equation 3, i.e.
$\textrm{argmin}_{\bm{x}}\lVert\ln\bm{y}-\ln\bm{Ax}\rVert^{2}_{2}+\lambda\|\bm{x}\|_{1}$,
might seem like an obvious choice. However, we have observed that such an
estimator produces very poor results in practice, and has many convergence
issues. Hence, we have not pursued it further in this work. Similar
observations have also been reported in [7, Sec. VII-A].

Let $S^{*}$ be the support of $\bm{x^{*}}$ (the true, unknown vector of $p$
viral loads) having size $s=|S^{*}|$. Under this condition of exact sparsity,
[18, Corollary 2] states that if the sensing matrix $\bm{A}$ satisfies the so-
called Restricted Eigenvalue Condition (REC, defined later) and the column
normalization condition, then the optimal solution $\bm{\hat{x}^{L}}$ of the
Lasso instance, with regularization parameter $\beta=4\sigma\sqrt{\frac{\ln
p}{n}}$, satisfies a high probability performance bound which increases in
direct proportion to the regularization parameter. However, [18] sets a
requirement on $\beta$ for this bound to hold: $\beta\geq
2\|\nabla\mathcal{L}\|_{\infty}$ where $\mathcal{L}(.)$ is the likelihood
function, i.e., $\beta$ should be greater than twice the $l_{\infty}$ norm of
the gradient of the quadratic loss in Lasso. This becomes particularly
restrictive when we apply it to the general case of WLasso from Equation 7,
where we have a separate regularization parameter $\beta_{k}$ for each element
of the signal. Instead, we can extend this by lower bounding each $\beta_{k}$
by the absolute value of its individual gradient term, i.e. by
$|(\bm{A}^{T}(\bm{y}-\bm{Ax^{*}}))_{k}|$.

Under this new condition on $\beta_{k}$, we have the following risk bounds for
the weighted and classical Lasso estimates ($\bm{\hat{x}^{WL}}$ and
$\bm{\hat{x}^{L}}$ respectively) when $\bm{A}$ and $\bm{y}$ follow the
conditions of Proposition 3 outlined later in the paper. Here $\rho_{\gamma}$
only depends on $\gamma$ and $\eta$ is a parameter associated with the
restricted eigenvalue condition (REC) of the sensing matrix $\bm{A}$:

$\|\bm{\hat{x}^{WL}}-\bm{x^{*}}\|_{2}^{2}\leq\frac{\rho_{\gamma}^{2}}{\eta}\sum_{k\in
S^{*}}\beta_{k}^{2}.$ (8)
$\|\bm{\hat{x}^{L}}-\bm{x^{*}}\|_{2}^{2}\leq\frac{\rho_{\gamma}^{2}}{\eta}s\beta^{2}.$
(9)

Looser bounds than those shown here can be obtained from an analysis of the
WLasso estimator using the typical Lasso bounding procedures outlined in [18].
Following from the prior discussion, if each $\beta_{k}$ in the WLasso
estimator is close to $|(\bm{A}^{T}(\bm{y}-\bm{Ax^{*}}))_{k}|$, then the
bounds on the WLasso are close to those of the oracle least squares estimator
[18, 2]. But practically, we cannot set $\beta_{k}$ to these values as the
weights should only depend on the observed data. However, we can still obtain
reasonable estimates of these weights based on the characteristics of the
data, as we do in this work.

$\textrm{Condition }\mathscr{C}1\textrm{ on
}\left(\\{\beta_{k}\\}_{k}\right):|(\bm{A}^{T}(\bm{y}-\bm{Ax^{*}}))_{k}|\leq\beta_{k}\quad\forall
k=1,...,p.$ (10)

We want the _smallest_ possible values of $\beta_{k}$ which would faithfully
satisfy the Condition $\mathscr{C}1$ with high probability. This serves as our
primary objective in deriving the data-dependent weights for our noise model
as stated in Section 2.3.

###  2.3 Assumptions and Data-Dependent Weights

Here we present the data-dependent weights and the underlying assumptions we
propose for the Lasso and WLasso estimators defined in Equation 6 and Equation
7, respectively. In this section, we outline the overall approach and a broad
proof sketch, while a full proof for these expressions can be found in the
Supplemental Material. We further demonstrate simulation results in Section 3,
and theoretical performance bounds in Section 2.4 using these weights.

We first impose a condition on the sensing matrix required for reconstruction
using the variants of the Lasso estimator. This is known as the Restricted
Eigenvalue Condition. It is defined below here, following [15, Chapter 11]:

A sensing matrix $\bm{A}$ of size $n\times p$ is said to obey the Restricted
Eigenvalue Condition (REC), if there exist constants $\kappa_{1},\kappa_{2}>0$
such that

$\lVert\bm{Ax}\rVert_{2}\geq\kappa_{2}\lVert\bm{x}\rVert_{2}-\kappa_{1}\lVert\bm{x}\rVert_{1},\quad\forall\bm{x}\in\text{R}^{p}.$
(11)

####  2.3.1 Rescaling and Recentering

The random Bernoulli sensing matrix which is suitable for pooled testing does
not obey the REC. Instead, we define a surrogate pooling matrix
$\bm{\tilde{A}}$ which would obey the REC and a surrogate measurement vector
$\bm{\tilde{y}}$. We want a complementary transformation to generate
$\bm{\tilde{y}},\bm{\tilde{A}}$ from $\bm{y},\bm{A}$. Ideally, we want the
Gram matrix of our surrogate pooling matrix to be as homogeneous as possible.
We invoke the following two commonly used conditions to obtain our surrogate
matrices:

$\text{E}\left(\bm{\tilde{A}}^{T}\bm{\tilde{A}}\right)=\bm{I_{p}}.$ (12)
$\text{E}\left(\bm{\tilde{A}}^{T}\left(\bm{\tilde{y}}-\bm{\tilde{A}x^{*}}\right)\right)=\bm{0}.$
(13)

In Equation 12, $\bm{I_{p}}$ stands for a $p\times p$ identity matrix.
Equation 12 helps us ensure that the REC defined in Equation 11 holds. We
impose the constraint in Equation 13 to make $\beta_{k}$ as small as possible,
while satisfying the Condition $\mathscr{C}1$. Based on the calculations in
[2, Appendix C-A], we obtain the following surrogate sensing matrix
$\bm{\tilde{A}}$ and surrogate measurement vector $\bm{\tilde{y}}$ given a
Bernoulli$(q)$ sensing matrix $\bm{A}$ and its associated measurement vector
$\bm{y}$:

$\bm{\tilde{A}}=\frac{\bm{A}}{\sqrt{nq(1-q)}}-\frac{q\bm{1}_{n\times
1}\bm{1}_{p\times 1}^{T}}{\sqrt{nq(1-q)}}.$ (14)
$\bm{\tilde{y}}=\frac{1}{(n-1)\sqrt{nq(1-q)}}\left(n\bm{y}-\sum_{l=1}^{n}y_{l}\bm{1}_{n\times
1}\right).$ (15)

We use the surrogate matrix $\bm{\tilde{A}}$ and surrogate measurement vector
$\bm{\tilde{y}}$ within the Lasso and WLasso estimators, as will be shown in
the next section. We note that $\bm{\tilde{A}}$ and $\bm{\tilde{y}}$ can be
computed entirely from $\bm{y},\bm{A},q$ without knowledge of the underlying
signal. Moreover, we note that the REC holds with high probability for
$\bm{\tilde{A}}$, as established in the lemma below which was proved in [2,
Appendix C-B].

######  Lemma 2.1.

There exist positive constants $c,c^{\prime},c^{\prime\prime}$ such that with
probability larger than $1-c^{\prime}\exp(-c^{\prime\prime}n)$,
$\bm{\tilde{A}}$ satisfies REC($\kappa_{1},\kappa_{2}$) with parameters
$\kappa_{1}:=\dfrac{c}{q(1-q)}\sqrt{\dfrac{\ln
p}{n}},\kappa_{2}:=\dfrac{1}{4}$.

####  2.3.2 Data dependent weights

Given the surrogate sensing matrix $\bm{\tilde{A}}$ and observations
$\bm{\tilde{y}}$, we redefine the Lasso and WLasso estimators via Equations
(16) and (17) respectively, as given below:

$\bm{\hat{x}^{L}}=\operatorname*{argmin}_{\bm{x}\in\text{R}^{p}}\|\bm{\tilde{y}}-\bm{\tilde{A}x}\|_{2}^{2}+\gamma\sum_{k=1}^{p}\beta|x_{k}|,$
(16)

where $\gamma>2$ is a constant and $\beta>0$ is a data-dependent scalar.

$\bm{\hat{x}^{WL}}=\operatorname*{argmin}_{\bm{x}\in\text{R}^{p}}\|\bm{\tilde{y}}-\bm{\tilde{A}x}\|_{2}^{2}+\gamma\sum_{k=1}^{p}\beta_{k}|x_{k}|,$
(17)

where $\gamma>2$ is a constant and $\beta_{k}>0$ is the $k$th data-dependent
scalar. The exact expressions of $\beta$ and $\beta_{k}$ depend on the
observed data and form the crux of our work.

In this section, we now upper bound the term
$\left|\left(\bm{\tilde{A}}^{T}\left(\bm{\tilde{y}}-\bm{\tilde{A}x^{*}}\right)\right)_{k}\right|$
and present data-dependent weights which satisfy Condition $\mathscr{C}1$ with
high-probability. We derive a single weight $\beta$ for Lasso in Proposition
1, and then derive the weights $\\{\beta_{k}\\}_{k=1}^{p}$ for the WLasso in
Proposition 2. The proofs of both propositions can be found in the
Supplemental Material.

######  Proposition 1.

Weight for Lasso:

Consider $\bm{A},\bm{\bar{R}}\in\text{R}^{n\times p}$ and define the
following:

$W:=\max_{i,j}\left(\bm{\bar{R}}^{T}\bm{A}\right)_{ij}\textrm{ for }1\leq
i\leq p,1\leq j\leq p,\quad\text{and}\quad\kappa:=\sigma\ln(1+q_{a})$

where
$\bm{\bar{R}}_{k,l}=\left(\frac{na_{l,k}-\sum_{l^{\prime}=1}^{n}a_{l^{\prime},k}}{n(n-1)q(1-q)}\right)^{2}$
for $k=1,\cdots,p;l=1,\cdots,n$.
Consider the following assumptions:

  * A1.

$nq\geq 12\max(q,1-q)\ln(p)$

  * A2.

$p\geq 2$

  * A3.

$\sigma<\frac{1}{\sqrt{2}\ln\left(1+q_{a}\right)}\left(\ln\left(\frac{1}{1-\left(1-\frac{1}{p^{3}}\right)^{1/n}}\right)\right)^{-1/2}$

  * A4.

$\bm{A}$ is a Bernoulli Sensing Matrix.

If the aforementioned assumptions hold, then there exist positive constants
$c$, $c^{\prime}$ such that with probability larger than
$1-\frac{c^{\prime}}{p}$, the choice

$\beta:=\kappa\hat{\Lambda}\sqrt{6W\ln(p)}+c\left(\frac{3\ln(p)}{n}+\frac{9\max(q^{2},(1-q)^{2})}{n^{2}q(1-q)}\ln(p)^{2}\right)\hat{\Lambda}$

satisfies Condition $\mathscr{C}1$ (defined earlier in Equation 10), where
$\hat{\Lambda}$ is an estimator of $\lVert\bm{x^{*}}\rVert_{1}$ given by

$\hat{\Lambda}:=\frac{\sum_{i=1}^{n}y_{i}+\sqrt{\sum_{i=1}^{n}y_{i}^{2}}\frac{\kappa\sqrt{6\ln(p)}}{1-\kappa\sqrt{2g(3\ln(p))}}}{nq-\sqrt{6nq(1-q)\ln(p)}-\max(q,1-q)\ln(p)},$

where for any $\theta\in\mathbb{R}$, we define

$g(\theta):=\ln\left(\frac{1}{1-\left(1-e^{-\theta}\right)^{1/n}}\right).$

Furthermore, $c=126$ works as long as $n\geq 20$.

######  Proposition 2.

Weights for WLasso

With the same notations and assumptions as in Proposition 1, there exist
positive constants $c$, $c^{\prime}$ such that with probability larger than
$1-\frac{c^{\prime}}{p}$, the choice (depending on $k$)

$\beta_{k}:=\sqrt{\bm{\bar{R}_{k}}^{T}\bm{y_{2}}}\frac{\kappa\sqrt{6\ln(p)}}{1-\kappa\sqrt{2g(3\ln(p))}}+c\left(\frac{3\ln(p)}{n}+\frac{9\max(q^{2},(1-q)^{2})}{n^{2}q(1-q)}\ln(p)^{2}\right)\hat{\Lambda}$

satisfies Condition $\mathscr{C}1$ (see Equation 10), where
$\bm{y_{2}}:=\bm{y}\odot\bm{y}$. Furthermore, $c=126$ works as long as $n\geq
20$.

Comments on Proposition 1 and Proposition 2:

  1. 1.

We now argue that Assumption A3 is reasonable for our RT-PCR noise model.
Since $n\geq 20$ and $p>n$, we have
$1-\left(1-\frac{1}{p^{3}}\right)^{\frac{1}{n}}>\frac{1}{np^{3}}$ by
Bernoulli’s inequality [28], [29, page 20]. Due to this, the expression
$\frac{1}{\sqrt{2}\ln\left(1+q_{a}\right)}\ln^{-\frac{1}{2}}\left(np^{3}\right)$
acts as a lower bound on the RHS of the inequality in Assumption A3 of
Proposition 1. This lower bound decreases as $n$ increases, as well as when
$q_{a}$ increases. Since we are operating in a compressive regime, $n$ can be
no greater than $p$. Moreover the largest possible value of $q_{a}$ is 1.
Hence the lower bound on the LHS is given by
$\dfrac{1}{2\ln(2)\sqrt{2\ln(p)}}$. Therefore, if we consider
$\sigma<\dfrac{1}{2\ln(2)\sqrt{2\ln(p)}}$, we always satisfy Assumption A3 of
Proposition 1. Given the small values of $\sigma$ required in practice for the
RT-PCR setting, as well as for the first-order expansion of the multiplicative
noise model described in Equation 4, this restriction on $\sigma$ is
reasonable and holds true for a large range of $p$. For example, if $p=100$,
we have $\sigma\leq 0.2377$.

  2. 2.

Under Assumption A1 of Proposition 1, we avoid values of $q$ very close to 0
or 1. Hence the weights $\beta$ or $\\{\beta_{k}\\}_{k=1}^{p}$ are not very
large in value, as can be seen from Proposition 1 and Proposition 2. Thereby
the upper bounds of the Lasso and WLasso estimators are also not very large,
as will be established in Proposition 3.

  3. 3.

With Assumptions A1 and A3 in place, we can show that $\hat{\Lambda}$, that is
the estimator for $\|\bm{x}^{*}\|_{1}$, is always positive. Note that
Assumption A3 can be re-written as $\kappa\sqrt{2g(3\ln p)}<1$ by setting
$\theta=3\ln p$ and using the definition of $\kappa$. This makes the numerator
of the expression for $\hat{\Lambda}$ positive, whenever A3 is true as each
element of $y$ is non-negative. We now argue that the denominator is also
positive, for which we denote $m_{q}:=\textrm{max}(q,1-q)$ and set
$nq=hm_{q}\ln p$ for $h\geq 12$ from Assumption A1. Then the denominator
becomes $\left((h-1)m_{q}-\sqrt{6(1-q)hm_{q}}\right)\ln p$ which is greater
than or equal to $\left((h-1)m_{q}-m_{q}\sqrt{6h}\right)\ln p$ using the
definition of $m_{q}$. For any $h\geq 8$, we see that this expression is
always positive, since $m_{q}$ and $\ln p$ are both positive. At this point,
we have established only lower bounds on $\hat{\Lambda}$ and have not proved
any upper bounds on its value in terms of $\|\bm{x^{*}}\|_{1}$. However, as
will be shown in Sec. 3, the estimates are close to $\|\bm{x^{*}}\|_{1}$
within a factor of two.

###  2.4 Performance Bounds

In this section, we establish performance bounds for Lasso and WLasso in the
context of multiplicative Gaussian Noise. For this, we present Proposition 3,
which is derived directly from [2, Proposition 1] that accounts for the
weighted $l_{1}$ regularizer defined in Equation 17, combined with
Propositions Proposition 1 and Proposition 2 derived here for our specific
noise model.

######  Proposition 3.

Performance Bounds for Lasso and WLasso

Fix $\varepsilon>0$ and consider the following:

$\displaystyle\beta_{max}:=\max_{k\in\\{1,\cdots,p\\}}\beta_{k},\beta_{min}:=\min_{k\in\\{1,\cdots,p\\}}\beta_{k},\rho_{\gamma}:=\gamma\frac{\gamma+2}{\gamma-2}$
$\displaystyle\bm{D}:=diag(\beta_{1},\cdots,\beta_{k},\cdots,\beta_{p}),$

where $\gamma,\beta,\\{\beta_{k}\\}$ are parameters of the estimators
presented in Section 2.2, and $\bm{D}$ is a diagonal matrix with the $k$th
diagonal element equal to $\beta_{k}$. For any vector $\bm{z}\in\text{R}^{p}$
and any set $S\subseteq\\{1,\cdots,p\\}$, define vector $\bm{z_{S}}$ such
$z_{S}(i)=z_{i}$ for all $i\in S$ and $z_{S}(i)=0$ for all $i\notin S$.

Now consider that the following assumptions hold true:

  * B1.

$\gamma>2$

  * B2.

$\\{\beta_{k}\\}_{k=1}^{p}$ and $\beta$ satisfy the Condition $\mathscr{C}1$
stated in Section 2.2

  * B3.

$\bm{\tilde{A}}$ satisfies the REC $(\kappa_{1},\kappa_{2})$ property stated
in Equation 11.

Then, there exists a universal constant $c>0$ such that for any set
$S\subseteq\\{1,\cdots,p\\}$ for which

$\lVert\bm{\beta_{S}}\rVert_{2}\leq\beta_{min}\frac{\kappa_{2}-\varepsilon}{\kappa_{1}\rho_{\gamma}},$

the WLasso estimator satisfies

$\lVert\bm{x^{*}}-\bm{\hat{x}^{WL}}\rVert_{2}\leq\frac{c\rho_{\gamma}}{\varepsilon^{2}}\lVert\bm{\beta_{S}}\rVert_{2}.$

Furthermore, for any set $S\subseteq\\{1,\ldots,p\\}$ with $s=|S|$ satisfying

$\sqrt{s}\leq\frac{\kappa_{2}-\varepsilon}{\kappa_{1}\rho_{\gamma}},$ (18)

for $\varepsilon>0$, the Lasso estimator satisfies

$\lVert\bm{x^{*}}-\bm{\hat{x}^{L}}\rVert_{2}\leq\frac{c\rho_{\gamma}}{\varepsilon^{2}}\beta\sqrt{s}.$
(19)

Comments on Proposition 3:

  1. 1.

Performance bounds for Lasso in [15, Exercise 11.3, Eqn. 11.44a] or [2,
Proposition 1] are derived for weakly sparse signals. In contrast, we operate
in the purely sparse regime for $\bm{x^{*}}$, as weakly sparse signal models
are not required for viral loads.

  2. 2.

Consider the performance bounds for $\bm{\hat{x}^{WL}}$ and $\bm{\hat{x}^{L}}$
and the Assumption B2 from Proposition 3. Taking these into account, we
observe that our motivation in Proposition 1 and Proposition 2 to find the
smallest possible weights which satisfies the Condition $\mathscr{C}1$ is well
justified. Ideally we would want weights $\beta_{k}$ such that
$\beta_{k}=|(\bm{A}^{T}(\bm{y}-\bm{Ax^{*}}))_{k}|\quad\forall k=1,...,p$.
However, since the input signal $\bm{x^{*}}$ is not observable, we can at best
produce high probability approximations, as done in Proposition 1 and
Proposition 2.

  3. 3.

Upper bounds for both estimators increase with the $s$, the $\ell_{0}$ norm of
$\bm{x^{*}}$. As $n$ increases, the upper bounds decrease, because the terms
$W$ in Proposition 1, and $\sqrt{\bm{\bar{R}_{k}}^{T}\bm{y_{2}}}$ as well as
$\dfrac{3c\ln p}{n}$ in Proposition 2, all decrease with $n$. These trends
with respect to $s$ and $n$ are quite intuitive.

  4. 4.

As $\|\bm{x^{*}}\|_{1}$ increases, we observe from Proposition 1 that all the
$y_{i}$ values will typically increase and hence $\hat{\Lambda}$ will
increase. Due to this, the upper bounds on
$\|\bm{x^{*}}-\bm{\hat{x}^{L}}\|_{2}$ and
$\|\bm{x^{*}}-\bm{\hat{x}^{WL}}\|_{2}$ for Lasso and WLasso respectively will
also increase. However, the _relative_ errors
$\dfrac{\|\bm{x^{*}}-\bm{\hat{x}^{WL}}\|_{2}}{\|\bm{x^{*}}\|_{1}}$ and
$\dfrac{\|\bm{x^{*}}-\bm{\hat{x}^{L}}\|_{2}}{\|\bm{x^{*}}\|_{1}}$ remain
constant. We emphasize the difference between this phenomenon and the trends
observed in Poisson compressed sensing [24, 2, 17, 25], where the relative
error actually _decreases_ with $\|\bm{x^{*}}\|_{1}$. The reason for this
difference is that the noise standard deviation is proportional to the _square
root_ of the signal value in case of Poisson noise, and proportional to the
signal value in the multiplicative noise model of RT-PCR (see Equation 4).

##  3 Numerical Results

Figure 1: RRMSE, Sensitivity and Specificity values for $q=0.5$, versus the
number of measurements $n$ and sparsity (fraction $f_{s}$ of people infected).
The top and bottom rows represent results for Lasso and WLasso, respectively.
Higher is better for Sensitivity and Specificity. However, the opposite holds
true for RRMSE.

(a) $q=0.05$

(b) $q=0.1$

(c) $q=0.25$

(d) $q=0.75$

(e) $q=0.05$

(f) $q=0.1$

(g) $q=0.25$

(h) $q=0.75$

Figure 2: RRMSE values for $q\in\\{0.05,0.1,0.25,0.75\\}$ (left to right),
versus the number of measurements $n$ and $f_{s}$ (fraction of people infected
out of a total of $p$). The top and bottom rows represent the results for
Lasso and WLasso, respectively. Lower is better.

We evaluate the derived expressions for the weights used in the Lasso and
WLasso estimators, using simulated signal reconstruction in pooled RT-PCR. In
particular, we use the cvxpy [30, 31] Python package to solve the WLasso
problem using $\bm{\tilde{y}},\bm{\tilde{A}}$. In our simulations, we take the
standard deviation of the (multiplicative) Gaussian noise to be 0.05. The
amplification factor $q_{a}$ is taken to be $0.95$. The value of $p$ (the
number of samples being tested) is fixed at 1000 and the number of pools $n$
is varied among $\\{150,200,300,375,500\\}$. The pooling matrix $\bm{A}$ is a
random Bernoulli matrix with each entry equal to $1$ with probability $q$, and
$0$ otherwise, freshly sampled for each variation. We experiment with values
of $q$ in $\\{0.05,0.1,0.25,0.5,0.75\\}$. We mostly focus on the case of
$q=0.5$ here - the complete set of plots will be made publicly available on
GitHub along with the code used for
simulation111https://github.com/sudoRicheek/Weighted-LASSO-MGN-Simulations.
The underlying ground truth of $\bm{x^{*}}$ has a $\ell_{0}$ norm given by
$f_{s}\times p$ where the fraction $f_{s}$ is sampled from
$\\{0.02,0.04,0.08,0.15\\}$. The non-zero entries of $\bm{x^{*}}$ are
uniformly randomly sampled from the interval $[1,1000]$, which reasonably
represents the viral loads of infected individuals. The other entries are
uniformly randomly sampled from $[0,0.2]$. A viral load of 0.2 is used as a
threshold to determine infected individuals from the reconstructed viral
loads. However, slight variations in this threshold do not alter the
Sensitivity and Specificity values stated in Figure 1.

Figure 3: General trends of RRMSE vs $\\{f_{s},n,\|\bm{x^{*}}\|_{1}\\}$ (left
to right). In each case, one of the parameters is varied, keeping the rest
fixed to default values.

For each combination of $n,f_{s},q$, we execute 200 independent simulations
and calculate averages of the RRMSE (Relative Root Mean-Squared-Error),
Sensitivity, and Specificity across the runs. The RRMSE is computed as
$\dfrac{\|\bm{x^{*}}-\bm{\hat{x}}\|_{2}}{\|\bm{x^{*}}\|_{2}}$, where
$\bm{\hat{x}}$ represents the estimate of the ground truth vector $\bm{x}$.
Let TP, TN, FP, FN denote the number of true positives, true negatives, false
positives and false negatives respectively. The sensitivity is defined as
$\dfrac{TP}{TP+FN}$, whereas the specificity is defined as
$\dfrac{TN}{TN+FP}$. Higher values are better for sensitivity and specificity,
whereas the opposite holds true for RRMSE. We report the measures as grid maps
for both Lasso and WLasso, with $n$ and $f_{s}$ being the independent
variables selected from the ranges mentioned earlier. For each combination, we
calculate a regularization factor $\gamma$ to be multiplied to the weight
$\beta$ for Lasso or the weights $\\{\beta_{k}\\}_{k=1}^{p}$ for WLasso, using
cross-validation on 5 preliminary runs.

We show the plots for the RRMSE values $(q=0.5)$ in the first column of Figure
1. As expected, the RRMSE increases with the $f_{s}$ (as a greater amount of
information is now compressed down to the same dimensions) and decreases with
the number of measurements (as more measurements capture more information).
Out of Lasso and Wlasso, neither estimator is consistently superior to the
other. This is, however unsurprising as the bounds we derive on the weights
are worst-case bounds and may not apply to the average case. Nevertheless, the
values obtained clearly demonstrate the suitability of the derived weights for
reconstruction. We show the corresponding values for the Sensitivity and
Specificity (for $q=0.5$) in the middle and rightmost columns of Figure 1
respectively. Interestingly, for higher fraction of people infected $(f_{s})$,
WLasso achieves a better specificity while being competitive with Lasso in the
sensitivity values. Both methods achieve high values on both measures at lower
sparsity levels.

Figure 4: Comparison of the estimator $\hat{\Lambda}$ with
$\|\bm{x^{*}}\|_{1}$ over a set of 1000 simulation runs (corresponding values
of the two quantities are plotted together).

We also compare the obtained results with the cases when the value of $q$ for
the sensing matrix is chosen to be from $\\{0.05,0.1,0.25,0.75\\}$. These
results are shown in Figure 2. As can be seen, smaller values of $q$ yield
lower RRMSE values as the average number of participants per pool decreases
with $q$. These trends will hold true as long as every sample participates in
two or more pools and no pool is left empty.

As can be seen from Propositions 1, 2 and 3, the RRMSE value scale as
$O(\sqrt{s})$ w.r.t. $s$, as $O(1/n)$ w.r.t. $n$ and as $O(1)$ w.r.t.
$\|\bm{x^{*}}\|_{1}$, keeping all other factors constant and set to their
default values. We verified experimentally that these trends hold true,
ignoring constant factors. The verification was performed over 500
independently generated signals. These trends are demonstrated in Figure 3.

Finally, the results in Propositions 1, 2 and 3 use an estimate of
$\|\bm{x^{*}}\|_{1}$, denoted as $\hat{\Lambda}$. In Figure 4, we demonstrate
that $\hat{\Lambda}$ is a good estimate for $\|\bm{x^{*}}\|_{1}$ and its value
empirically never crosses $2\|\bm{x^{*}}\|_{1}$. This is shown for 1000
independent simulations. As an example, the average value of
$\|\bm{x^{*}}\|_{1}$ across 1000 simulations was $\sim 19,900$ with a standard
deviation of $\sim 3500$, whereas the average value of $\hat{\Lambda}$ was
$\sim 28,900$ with a standard deviation of $\sim 5200$.

##  4 Conclusion

Despite extensive work on the theoretical guarantees for compressed sensing in
the additive Gaussian Noise setting, current literature lacks performance
bounds for the case of multiplicative Gaussian Noise which describes the noise
in the scenario of RT-PCR Group Testing. In this work we develop performance
bounds for the weighted and unweighted Lasso problems in the case of
multiplicative Gaussian Noise, and derive expressions for weights
corresponding to these bounds. We then show via simulation that our weights
yield good performance in practice. We hope that our efforts inspire future
work on more varied as well as general noise models in compressed sensing. A
full analysis of performance bounds for the noise model without use of Taylor
expansion, along the lines of [19], is an important avenue for future work.
Our current work considers randomly generated Bernoulli matrices as pooling
matrices. Extending our analysis to the important case of deterministic
matrices [1] is another useful direction for future work. Multiplicative
noise, albeit of a different form, also shows up in some other modalities such
as synthetic aperture radar [32, 33] and photo-acoustic tomography [34,
Equation 17]. Developing compressed sensing bounds in such modalities is also
another future research direction.

## References

  * [1] S. Ghosh, R. Agarwal, M. A. Rehan, S. Pathak, P. Agarwal, Y. Gupta, S. Consul, N. Gupta, Ritika, R. Goenka, A. Rajwade, M. Gopalkrishnan, A compressed sensing approach to pooled RT-PCR testing for COVID-19 detection, IEEE Open Journal of Signal Processing 2 (2021) 248–264.  doi:10.1109/ojsp.2021.3075913.
  * [2] X. J. Hunt, P. Reynaud-Bouret, V. Rivoirard, L. Sansonnet, R. Willett, A data-dependent weighted LASSO under Poisson noise, IEEE Transactions on Information Theory 65 (3) (2018) 1589–1613.  doi:10.1109/TIT.2018.2869578.
  * [3] N. Jawerth, How is the COVID-19 virus detected using real time RT-PCR?, https://www.iaea.org/newscenter/news/how-is-the-covid-19-virus-detected-using-real-time-rt-pcr.
  * [4] List of countries implementing pool testing strategy against COVID-19, https://en.wikipedia.org/wiki/List_of_countries_implementing_pool_testing_strategy_against_COVID-19, last retrieved, Oct 2021.
  * [5] N. Shental, et al., Efficient high throughput SARS-CoV-2 testing to detect asymptomatic carriers, Sci. Adv. 6 (37) (Sep. 2020).  doi:10.1126/sciadv.abc5961.
  * [6] A. Heidarzadeh, K. Narayanan, Two-stage adaptive pooling with RT-qPCR for COVID-19 screening, in: ICASSP, 2021.
  * [7] R. Goenka, S. Cao, C. Wong, A. Rajwade, D. Baron, Contact tracing information improves the performance of group testing algorithms (2021).
URL https://arxiv.org/abs/2106.02699

  * [8] R. Goenka, S.-J. Cao, C.-W. Wong, A. Rajwade, D. Baron, Contact tracing enhances the efficiency of covid-19 group testing, in: ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2021, pp. 8168–8172.
  * [9] R. Dorfman, The Detection of Defective Members of Large Populations, The Annals of Mathematical Statistics 14 (4) (1943) 436 – 440.  doi:10.1214/aoms/1177731363.
  * [10] Israelis introduce a method for accelerated covid-19 testing.
URL https://www.israel21c.org/israelis-introduce-method-for-accelerated-
covid-19-testing/

  * [11] Corona pool testing increases worldwide capacities many times over.
URL https://healthcare-in-europe.com/en/news/corona-pool-testing-increases-
worldwide-capacities-many-times-over.html

  * [12] D. B. Larremore, B. Wilder, E. Lester, S. Shehata, J. M. Burke, J. A. Hay, M. Tambe, M. Mina, R. Parker, Test sensitivity is secondary to frequency and turnaround time for COVID-19 screening, Science Advances 7 (1) (2021).
  * [13] D. Donoho, Compressed sensing, IEEE Transactions on Information Theory 52 (4) (2006) 1289–1306.  doi:10.1109/TIT.2006.871582.
  * [14] M. Aldridge, O. Johnson, J. Scarlett, et al., Group testing: an information theory perspective, Foundations and Trends® in Communications and Information Theory 15 (3-4) (2019) 196–392.
  * [15] T. Hastie, R. Tibshirani, M. Wainwright, Statistical Learning with Sparsity: The LASSO and Generalizations, CRC Press, 2015.
  * [16] J. Huang, T. Zhang, The benefit of group sparsity, The Annals of Statistics 38 (4) (2010) 1978 – 2004.
  * [17] Y. Li, G. Raskutti, Minimax optimal convex methods for Poisson inverse problems under $\ell_{q}$ -ball sparsity, IEEE Transactions on Information Theory 64 (8) (2018) 5498–5512.  doi:10.1109/TIT.2018.2850365.
  * [18] S. Negahban, P. Ravikumar, M. J. Wainwright, B. Yu, A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers, Statistical Science 27 (4) (2012) 538–557.
  * [19] R. Chatterjee, Reconstruction of sparse signals under the influence of multiplicative log-normal noise using l1-regularization, https://tinyurl.com/4w8rr5mz, MSc Thesis, IIT Bombay (2021).
  * [20] E. A. Daniel, B. H. Esakialraj L, A. S, K. Muthuramalingam, R. Karunaianantham, L. P. Karunakaran, M. Nesakumar, M. Selvachithiram, S. Pattabiraman, S. Natarajan, S. P. Tripathy, L. E. Hanna, Pooled Testing Strategies for SARS-CoV-2 diagnosis: A comprehensive review, Diagn Microbiol Infect Dis 101 (2) (2021) 115432.
  * [21] Y. Karlen, A. McNair, S. Perseguers, C. Mazza, N. Mermod, Statistical significance of quantitative pcr, BMC bioinformatics 8 (2007) 1–16.
  * [22] T. Arildsen, T. Larsen, Compressed sensing with linear correlation between signal and measurement noise, Signal Processing 98 (2014) 275–283.
  * [23] J. H. Pollard, A handbook of numerical and statistical techniques: with examples mainly from the life sciences, CUP Archive, 1979.
  * [24] A. Rajwade, K. S. Gurumoorthy, Two penalized estimators based on variance stabilization transforms for sparse compressive recovery with Poisson measurement noise, Signal Processing 188 (2021) 108186.
  * [25] P. Bohra, D. Garg, K. S. Gurumoorthy, A. Rajwade, Variance-stabilization-based compressive inversion under Poisson or Poisson–Gaussian noise with analytical bounds, Inverse Problems 35 (10) (2019) 105006.
  * [26] P. Gopal, S. Chandran, I. Svalbe, A. Rajwade, Low radiation tomographic reconstruction with and without template information, Signal Processing 175 (2020) 107582.
  * [27] F.-X. Dupé, J. M. Fadili, J.-L. Starck, A proximal iteration for deconvolving Poisson noisy images using sparse representations, IEEE Transactions on Image Processing 18 (2) (2009) 310–321.
  * [28] Bernoulli’s inequality, https://en.wikipedia.org/wiki/Bernoulli’s_inequality.
  * [29] D. A. Brannan, A first course in mathematical analysis, Cambridge University Press, 2006.
  * [30] S. Diamond, S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, Journal of Machine Learning Research 17 (83) (2016) 1–5.
  * [31] A. Agrawal, R. Verschueren, S. Diamond, S. Boyd, A rewriting system for convex optimization problems, Journal of Control and Decision 5 (1) (2018) 42–60.
  * [32] R. Pournaghshband, M. Modarres-Hashemi, A novel block compressive sensing algorithm for SAR image formation, Signal Processing (2023).
  * [33] G. Aubert, J.-F. Aujol, A variational approach to removing multiplicative noise, SIAM journal on applied mathematics 68 (4) (2008) 925–946.
  * [34] S. Arridge, P. Beard, M. Betcke, B. Cox, N. Huynh, F. Lucka, O. Ogunlade, E. Zhang, Accelerated high-resolution photoacoustic tomography via compressed sensing, Physics in Medicine & Biology 61 (24) (2016) 8908.