Two-Stage Decoding Algorithm and Bounds for Group Testing with Prior Statistics
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_ | 1866914359415930880 |
|---|---|
| author | Portnoy, Ayelet C. Solomon, Amit Cohen, Alejandro |
| author_facet | Portnoy, Ayelet C. Solomon, Amit Cohen, Alejandro |
| contents | In this paper, we propose an efficient two-stage decoding algorithm for non-adaptive Group Testing (GT) with general correlated prior statistics. The proposed solution can be applied to any correlated statistical prior represented in trellis, e.g., finite state machines and Markov processes. We introduce a variation of List Viterbi Algorithm (LVA) to enable accurate recovery using much fewer tests than objectives, which efficiently gains from the correlated prior statistics structure. We also provide a sufficiency bound to the number of pooled tests required by any Maximum A Posteriori (MAP) decoder with an arbitrary correlation, i.e., dependence between infected items. Our numerical results demonstrate that the proposed two-stage decoding GT (2SDGT) algorithm can obtain the optimal MAP performance with feasible complexity in practical regimes, such as with COVID-19 and sparse signal recovery applications, and reduce in the scenarios tested the number of pooled tests by at least $25\%$ compared to existing classical low complexity GT algorithms. Moreover, we analytically characterize the complexity of the proposed 2SDGT algorithm that guarantees its efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10018 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Two-Stage Decoding Algorithm and Bounds for Group Testing with Prior Statistics Portnoy, Ayelet C. Solomon, Amit Cohen, Alejandro Information Theory Quantitative Methods Applications In this paper, we propose an efficient two-stage decoding algorithm for non-adaptive Group Testing (GT) with general correlated prior statistics. The proposed solution can be applied to any correlated statistical prior represented in trellis, e.g., finite state machines and Markov processes. We introduce a variation of List Viterbi Algorithm (LVA) to enable accurate recovery using much fewer tests than objectives, which efficiently gains from the correlated prior statistics structure. We also provide a sufficiency bound to the number of pooled tests required by any Maximum A Posteriori (MAP) decoder with an arbitrary correlation, i.e., dependence between infected items. Our numerical results demonstrate that the proposed two-stage decoding GT (2SDGT) algorithm can obtain the optimal MAP performance with feasible complexity in practical regimes, such as with COVID-19 and sparse signal recovery applications, and reduce in the scenarios tested the number of pooled tests by at least $25\%$ compared to existing classical low complexity GT algorithms. Moreover, we analytically characterize the complexity of the proposed 2SDGT algorithm that guarantees its efficiency. |
| title | Two-Stage Decoding Algorithm and Bounds for Group Testing with Prior Statistics |
| topic | Information Theory Quantitative Methods Applications |
| url | https://arxiv.org/abs/2402.10018 |