Quantitative Group Testing and Pooled Data in the Linear Regime with Sublinear Tests
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918136489443328 |
|---|---|
| author | Tan, Nelvin Cobo, Pablo Pascual Venkataramanan, Ramji |
| author_facet | Tan, Nelvin Cobo, Pablo Pascual Venkataramanan, Ramji |
| contents | 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 in the pool belonging to each category. A prominent special case is quantitative group testing (QGT), which is the case of pooled data with two categories. We consider these problems in the non-adaptive and linear regime, where the fraction of items in each category is of constant order. We propose a scheme with a spatially coupled Bernoulli test matrix and an efficient approximate message passing (AMP) algorithm for recovery. We rigorously characterize its asymptotic performance in both the noiseless and noisy settings, and prove that in the noiseless case, the AMP algorithm achieves almost-exact recovery with a number of tests sublinear in the total number of items $p$. Although there exist other efficient schemes for noiseless QGT and pooled data that achieve recovery with order-optimal sample complexity ($Θ(\frac{p}{\log p})$ tests), there are no guarantees on their performance in the presence of noise, even at low noise-levels. In comparison, our scheme achieves recovery in the noiseless case with a number of tests sublinear in $p$, and its performance degrades gracefully in the presence of noise. Numerical simulations illustrate the benefits of the spatially coupled scheme at finite dimensions, showing that it outperforms i.i.d. test designs as well as other recovery algorithms based on convex programming. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00385 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantitative Group Testing and Pooled Data in the Linear Regime with Sublinear Tests Tan, Nelvin Cobo, Pablo Pascual Venkataramanan, Ramji Information Theory Signal Processing 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 in the pool belonging to each category. A prominent special case is quantitative group testing (QGT), which is the case of pooled data with two categories. We consider these problems in the non-adaptive and linear regime, where the fraction of items in each category is of constant order. We propose a scheme with a spatially coupled Bernoulli test matrix and an efficient approximate message passing (AMP) algorithm for recovery. We rigorously characterize its asymptotic performance in both the noiseless and noisy settings, and prove that in the noiseless case, the AMP algorithm achieves almost-exact recovery with a number of tests sublinear in the total number of items $p$. Although there exist other efficient schemes for noiseless QGT and pooled data that achieve recovery with order-optimal sample complexity ($Θ(\frac{p}{\log p})$ tests), there are no guarantees on their performance in the presence of noise, even at low noise-levels. In comparison, our scheme achieves recovery in the noiseless case with a number of tests sublinear in $p$, and its performance degrades gracefully in the presence of noise. Numerical simulations illustrate the benefits of the spatially coupled scheme at finite dimensions, showing that it outperforms i.i.d. test designs as well as other recovery algorithms based on convex programming. |
| title | Quantitative Group Testing and Pooled Data in the Linear Regime with Sublinear Tests |
| topic | Information Theory Signal Processing |
| url | https://arxiv.org/abs/2408.00385 |