Density of Pooling Matrices vs. Sparsity of Signals for Group Testing Problems

Jin-Taek SEONG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.5   pp.1081-1084
Publication Date: 2019/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDL8200
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
group testing,  lower bound,  pooling matrix,  sparsity,  

Full Text: PDF(207.5KB)>>
Buy this Article




Summary: 
In this paper, we consider a group testing (GT) problem. We derive a lower bound on the probability of error for successful decoding of defected binary signals. To this end, we exploit Fano's inequality theorem in the information theory. We show that the probability of error is bounded as an entropy function, a density of a pooling matrix and a sparsity of a binary signal. We evaluate that for decoding of highly sparse signals, the pooling matrix is required to be dense. Conversely, if dense signals are needed to decode, the sparse pooling matrix should be designed to achieve the small probability of error.