Robust Non-adaptive Group Testing under Errors in Group Membership Specifications

Shuvayan Banerjee, Radhendushka Srivastava, James Saunderson, Ajit RajwadearXiv 2024 · DOI · arXiv

Introduction

Group testing is a well-established strategy for efficiently identifying a small number of "defective" items within a large population. By pooling samples and testing them collectively, researchers can significantly reduce the number of required tests from $p$ (the number of individuals) to $n$ (the number of pools), where $n \ll p$. This approach is particularly vital in public health crises, such as the COVID-19 pandemic, where testing resources are often strained.

However, the practical implementation of group testing faces a significant hurdle: human error. Standard group testing algorithms rely on a precise pooling matrix—a blueprint specifying which samples are included in which pools. In high-pressure laboratory environments, technicians may inadvertently swap samples or omit a tube, leading to "bit-flip" errors in the matrix. Traditional recovery methods, such as the standard LASSO, are highly sensitive to these model mismatches, often resulting in biased estimates or a complete failure to identify positive cases. This paper introduces the Optimal Debiased Robust LASSO Test Method (ODRLT), a framework designed to maintain high accuracy even when the pooling process itself is flawed.

The ODRLT Framework

The authors approach the problem by modeling pooling errors as a sparse outlier vector. The relationship between the test results $y$ and the sample statuses $\beta^*$ is defined by the linear system:

$$y = A\beta^* + \delta^* + \eta$$

In this model, $A$ represents the intended pooling matrix, $\beta^*$ is the vector of individual sample statuses (e.g., viral loads), $\eta$ is the measurement noise, and $\delta^*$ is a sparse vector representing the errors introduced during the pooling process. The ODRLT method operates through a three-stage pipeline:

  1. Robust Estimation: The method first employs a "Robust LASSO" formulation that applies an $\ell_1$ penalty to both the signal $\beta$ and the error vector $\delta$. This initial step provides a joint estimate of the sample statuses and the specific pooling mistakes.
  2. Optimal Debiasing: Because $\ell_1$ regularization inherently introduces bias, the authors developed a novel debiasing optimization. They solve a convex optimization problem to identify an optimal weighting matrix $W$. This matrix is designed to minimize the variance of the final estimate while neutralizing the bias caused by the matrix errors. A key innovation is ensuring $W$ is "nearly orthogonal" to the error structure, effectively filtering out the lab mistakes.
  3. Hypothesis Testing: Finally, using the debiased estimates, the framework performs statistical hypothesis tests. This allows the system to determine with statistical confidence whether a sample is truly positive or if a specific pool result is an outlier that should be disregarded.

Experimental Methodology

To validate the ODRLT framework, the researchers conducted extensive simulations using both synthetic data and real-world parameters:

  • Synthetic Signals: The study evaluated signals with $p=500$ elements, drawing non-zero values from Uniform and Power-law distributions to simulate varying viral loads.
  • Pooling Designs: The method was tested against various matrix structures, including Random Rademacher, Bernoulli, and "doubly-regular" matrices.
  • Real-world Context: To ground the study in practical application, the authors utilized an empirical distribution of viral loads from a COVID-19 RT-PCR study (Buchan et al., 2020), ensuring the model could handle the dynamic range of actual clinical samples.

Key Insights and Results

The ODRLT method demonstrates that pooling errors do not have to compromise the integrity of group testing. By treating these errors as sparse outliers rather than general noise, the framework successfully separates the "truth" of the samples from the "mistakes" of the laboratory work.

Performance Metrics

  • High Accuracy: ODRLT consistently outperformed standard debiased LASSO and robust baselines like RANSAC. In several test scenarios, the method achieved sensitivity and specificity levels near 1.0, even when 10% of the pools contained membership errors.
  • Variance Reduction: The optimization of the $W$ matrix resulted in a variance reduction of approximately 1/3 compared to standard debiasing techniques. This reduction significantly increases the power of the subsequent statistical tests.
  • Noise Robustness: The framework proved resilient across various noise profiles, including Gaussian, Uniform, and heavy-tailed Generalized Gaussian noise, suggesting broad applicability across different types of diagnostic hardware.

Computational Efficiency

While the convex optimization required to find the weighting matrix $W$ is computationally intensive, the authors highlight that this is a one-time cost. For a fixed pooling design (e.g., a standard 96-well plate layout), $W$ can be pre-calculated and reused for every subsequent batch of tests, making the real-time decoding process extremely fast.

Limitations and Future Directions

Despite its strengths, the ODRLT framework has limitations. The current model assumes a linear relationship where the viral load in a pool is the sum of individual loads. While accurate for quantitative tests like RT-PCR, this may require adaptation for purely qualitative (binary) tests. Additionally, while the one-time cost of $W$ is manageable, scaling the initial optimization to tens of thousands of samples remains a challenge.

Future research may explore "permutation noise"—where entire rows or columns of the matrix are swapped—and the application of these robust techniques to non-linear measurement models, such as those found in tropical group testing.

Summary updated

Abstract

Given $p$ samples, each of which may or may not be defective, group testing (GT) aims to determine their defect status by performing tests on $n < p$ `groups', where a group is formed by mixing a subset of the $p$ samples. Assuming that the number of defective samples is very small compared to $p$, GT algorithms have provided excellent recovery of the status of all $p$ samples with even a small number of groups. Most existing methods, however, assume that the group memberships are accurately specified. This assumption may not always be true in all applications, due to various resource constraints. Such errors could occur, eg, when a technician, preparing the groups in a laboratory, unknowingly mixes together an incorrect subset of samples as compared to what was specified. We develop a new GT method, the Debiased Robust Lasso Test Method (DRLT), that handles such group membership specification errors. The proposed DRLT method is based on an approach to debias, or reduce the inherent bias in, estimates produced by Lasso, a popular and effective sparse regression technique. We also provide theoretical upper bounds on the reconstruction error produced by our estimator. Our approach is then combined with two carefully designed hypothesis tests respectively for (i) the identification of defective samples in the presence of errors in group membership specifications, and (ii) the identification of groups with erroneous membership specifications. The DRLT approach extends the literature on bias mitigation of statistical estimators such as the LASSO, to handle the important case when some of the measurements contain outliers, due to factors such as group membership specification errors. We present numerical results which show that our approach outperforms several baselines and robust regression techniques for identification of defective samples as well as erroneously specified groups.
BibTeX
@misc{banerjee2024robust,
  author = {Shuvayan Banerjee and Radhendushka Srivastava and James Saunderson and Ajit Rajwade},
  title = {{Robust Non-adaptive Group Testing under Errors in Group Membership Specifications}},
  year = {2024},
  eprint = {2409.05345},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.05345},
}
Figure