  We propose `Tapestry', a novel approach to pooled testing with application to
COVID-19 testing with quantitative Reverse Transcription Polymerase Chain
Reaction (RT-PCR) that can result in shorter testing time and conservation of
reagents and testing kits. Tapestry combines ideas from compressed sensing and
combinatorial group testing with a novel noise model for RT-PCR used for
generation of synthetic data. Unlike Boolean group testing algorithms, the
input is a quantitative readout from each test and the output is a list of
viral loads for each sample relative to the pool with the highest viral load.
While other pooling techniques require a second confirmatory assay, Tapestry
obtains individual sample-level results in a single round of testing, at
clinically acceptable false positive or false negative rates. We also propose
designs for pooling matrices that facilitate good prediction of the infected
samples while remaining practically viable. When testing $n$ samples out of
which $k \ll n$ are infected, our method needs only $O(k \log n)$ tests when
using random binary pooling matrices, with high probability. However, we also
use deterministic binary pooling matrices based on combinatorial design ideas
of Kirkman Triple Systems to balance between good reconstruction properties and
matrix sparsity for ease of pooling. In practice, we have observed the need for
fewer tests with such matrices than with random pooling matrices. This makes
Tapestry capable of very large savings at low prevalence rates, while
simultaneously remaining viable even at prevalence rates as high as 9.5\%.
Empirically we find that single-round Tapestry pooling improves over two-round
Dorfman pooling by almost a factor of 2 in the number of tests required. We
validate Tapestry in simulations and wet lab experiments with oligomers in
quantitative RT-PCR assays. Lastly, we describe use-case scenarios for
deployment.
