Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme
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_ | 1866913660512763904 |
|---|---|
| author | Li, Xiaxin Mazumdar, Arya |
| author_facet | Li, Xiaxin Mazumdar, Arya |
| contents | In Group Testing, the objective is to identify $K$ defective items out of $N$, $K\ll N$, by testing pools of items together and using the least amount of tests possible. Recently, a fast decoding method based on binary splitting (Price and Scarlett, 2020) has been proposed that simultaneously achieve optimal number of tests and decoding complexity for Non-Adaptive Probabilistic Group Testing (NAPGT). However, the method works only when the test results are noiseless. In this paper, we further study the binary splitting method and propose (1) A NAPGT scheme that generalizes the original binary splitting method from the noiseless case into tests with $ρ$ proportion of false positives (the $ρ$-False Positive Channel), where $ρ$ is a constant, with asymptotically-optimal number of tests and decoding complexity, i.e. $\mathcal{O}(K\log N)$, and (2) A NAPGT scheme in the presence of both false positives and false negatives in test outcomes, improving and generalizing the work of Price, Scarlett and Tan~\cite{price2023fast} in two ways: First, under $ρ$-proportion of test results flipped ($ρ$-Binary Symmetric Channel) and within the general sublinear regime $K=Θ(N^α)$ where $0<α<1$, our algorithm has a decoding complexity of $\mathcal{O}(ε^{-2}K^{1+ε})$ where $ε>0$ is a constant parameter. Second, when the false negative flipping probability $ρ'$ satisfies $ρ'=\mathcal{O}(K^{-ε})$ and the false positive flipping probability $ρ$ is a constant, we can simultaneously achieve $\mathcal{O}(ε^{-1}K\log N)$ for both the number of tests and the decoding complexity. It remains open to achieve these optimals under the general BSC. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14566 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme Li, Xiaxin Mazumdar, Arya Information Theory Discrete Mathematics Data Structures and Algorithms In Group Testing, the objective is to identify $K$ defective items out of $N$, $K\ll N$, by testing pools of items together and using the least amount of tests possible. Recently, a fast decoding method based on binary splitting (Price and Scarlett, 2020) has been proposed that simultaneously achieve optimal number of tests and decoding complexity for Non-Adaptive Probabilistic Group Testing (NAPGT). However, the method works only when the test results are noiseless. In this paper, we further study the binary splitting method and propose (1) A NAPGT scheme that generalizes the original binary splitting method from the noiseless case into tests with $ρ$ proportion of false positives (the $ρ$-False Positive Channel), where $ρ$ is a constant, with asymptotically-optimal number of tests and decoding complexity, i.e. $\mathcal{O}(K\log N)$, and (2) A NAPGT scheme in the presence of both false positives and false negatives in test outcomes, improving and generalizing the work of Price, Scarlett and Tan~\cite{price2023fast} in two ways: First, under $ρ$-proportion of test results flipped ($ρ$-Binary Symmetric Channel) and within the general sublinear regime $K=Θ(N^α)$ where $0<α<1$, our algorithm has a decoding complexity of $\mathcal{O}(ε^{-2}K^{1+ε})$ where $ε>0$ is a constant parameter. Second, when the false negative flipping probability $ρ'$ satisfies $ρ'=\mathcal{O}(K^{-ε})$ and the false positive flipping probability $ρ$ is a constant, we can simultaneously achieve $\mathcal{O}(ε^{-1}K\log N)$ for both the number of tests and the decoding complexity. It remains open to achieve these optimals under the general BSC. |
| title | Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme |
| topic | Information Theory Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.14566 |