Sparsity-Constrained Community-Based Group Testing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909141671346176 |
|---|---|
| author | Jain, Sarthak Cardone, Martina Mohajer, Soheil |
| author_facet | Jain, Sarthak Cardone, Martina Mohajer, Soheil |
| contents | In this work, we consider the sparsity-constrained community-based group testing problem, where the population follows a community structure. In particular, the community consists of $F$ families, each with $M$ members. A number $k_f$ out of the $F$ families are infected, and a family is said to be infected if $k_m$ out of its $M$ members are infected. Furthermore, the sparsity constraint allows at most $ρ_T$ individuals to be grouped in each test. For this sparsity-constrained community model, we propose a probabilistic group testing algorithm that can identify the infected population with a vanishing probability of error and we provide an upper-bound on the number of tests. When $k_m = Θ(M)$ and $M \gg \log(FM)$, our bound outperforms the existing sparsity-constrained group testing results trivially applied to the community model. If the sparsity constraint is relaxed, our achievable bound reduces to existing bounds for community-based group testing. Moreover, our scheme can also be applied to the classical dilution model, where it outperforms existing noise-level-independent schemes in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12419 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparsity-Constrained Community-Based Group Testing Jain, Sarthak Cardone, Martina Mohajer, Soheil Information Theory In this work, we consider the sparsity-constrained community-based group testing problem, where the population follows a community structure. In particular, the community consists of $F$ families, each with $M$ members. A number $k_f$ out of the $F$ families are infected, and a family is said to be infected if $k_m$ out of its $M$ members are infected. Furthermore, the sparsity constraint allows at most $ρ_T$ individuals to be grouped in each test. For this sparsity-constrained community model, we propose a probabilistic group testing algorithm that can identify the infected population with a vanishing probability of error and we provide an upper-bound on the number of tests. When $k_m = Θ(M)$ and $M \gg \log(FM)$, our bound outperforms the existing sparsity-constrained group testing results trivially applied to the community model. If the sparsity constraint is relaxed, our achievable bound reduces to existing bounds for community-based group testing. Moreover, our scheme can also be applied to the classical dilution model, where it outperforms existing noise-level-independent schemes in the literature. |
| title | Sparsity-Constrained Community-Based Group Testing |
| topic | Information Theory |
| url | https://arxiv.org/abs/2403.12419 |