Bitwise MAP Estimation for Group Testing Based on Holographic Transformation

Tadashi WADAYAMA  Taisuke IZUMI  Kazushi MIMURA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.12   pp.2147-2154
Publication Date: 2016/12/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory and Techniques
group testing,  holographic transformation,  normal factor graph,  

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

The main contribution of this paper is a non-trivial expression, that is called dual expression, of the posterior values for non-adaptive group testing problems. The dual expression is useful for exact bitwise MAP estimation. We assume a simplest non-adaptive group testing scenario including N-objects with binary status and M-tests. If a group contains one or more positive object, the test result for the group is assumed to be one; otherwise, the test result becomes zero. Our inference problem is to evaluate the posterior probabilities of the objects from the observation of M-test results and the prior probabilities for objects. The derivation of the dual expression of posterior values can be naturally described based on a holographic transformation to the normal factor graph (NFG) representing the inference problem. In order to handle OR constraints in the NFG, we introduce a novel holographic transformation that converts an OR function to a function similar to an EQUAL function.