Repository logo
 

Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Venkataramanan, Ramji  ORCID logo  https://orcid.org/0000-0001-7915-5432
Tan, Nelvin 
Pascual Cobo, Pablo 
Scarlett, Jonathan 

Abstract

In the pooled data problem, the goal is to identify the categories associated with a large collection of items via a sequence of pooled tests. Each pooled test reveals the number of items of each category within the pool. We study an approximate message passing (AMP) algorithm for estimating the categories and rigorously characterize its performance, in both the noiseless and noisy settings. For the noiseless setting, we show that the AMP algorithm is equivalent to one recently proposed by El Alaoui et~al. Our results provide a rigorous version of their performance guarantees, previously obtained via non-rigorous techniques. For the case of pooled data with two categories, known as quantitative group testing (QGT), we use the AMP guarantees to compute precise limiting values of the false positive rate and the false negative rate. Though the pooled data problem and QGT are both instances of estimation in a linear model, existing AMP theory cannot be directly applied since the design matrices are binary valued. The key technical ingredient in our analysis is a rigorous asymptotic characterization of AMP for generalized linear models defined via generalized white noise design matrices. This result, established using a recent universality result of Wang et al., is of independent interest. Our theoretical results are validated by numerical simulations. For comparison, we propose estimators based on convex relaxation and iterative thresholding, without providing theoretical guarantees. The simulations indicate that AMP outperforms the convex estimator for noiseless pooled data and QGT, but the convex estimator performs slightly better for noisy pooled data with three categories when the number of observations is small.

Description

Keywords

Journal Title

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE

Conference Name

Journal ISSN

2577-0187
2577-0187

Volume Title

Publisher

Publisher DOI

Publisher URL