تقرير
Group Testing using left-and-right-regular sparse-graph codes
| العنوان: | Group Testing using left-and-right-regular sparse-graph codes |
|---|---|
| المؤلفون: | Vem, Avinash, Janakiraman, Nagaraj T., Narayanan, Krishna R. |
| سنة النشر: | 2017 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Information Theory |
| الوصف: | We consider the problem of non-adaptive group testing of $N$ items out of which $K$ or less items are known to be defective. We propose a testing scheme based on left-and-right-regular sparse-graph codes and a simple iterative decoder. We show that for any arbitrarily small $\epsilon>0$ our scheme requires only $m=c_\epsilon K\log \frac{c_1N}{K}$ tests to recover $(1-\epsilon)$ fraction of the defective items with high probability (w.h.p) i.e., with probability approaching $1$ asymptotically in $N$ and $K$, where the value of constants $c_\epsilon$ and $\ell$ are a function of the desired error floor $\epsilon$ and constant $c_1=\frac{\ell}{c_\epsilon}$ (observed to be approximately equal to 1 for various values of $\epsilon$). More importantly the iterative decoding algorithm has a sub-linear computational complexity of $\mathcal{O}(K\log \frac{N}{K})$ which is known to be optimal. Also for $m=c_2 K\log K\log \frac{N}{K}$ tests our scheme recovers the \textit{whole} set of defective items w.h.p. These results are valid for both noiseless and noisy versions of the problem as long as the number of defective items scale sub-linearly with the total number of items, i.e., $K=o(N)$. The simulation results validate the theoretical results by showing a substantial improvement in the number of tests required when compared to the testing scheme based on left-regular sparse-graphs. Comment: Part of this work is submitted to IEEE International Symposium on Information Theory 2017 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1701.07477 |
| رقم الأكسشن: | edsarx.1701.07477 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |