论文标题
基于模型和基于图的先验用于小组测试
Model-Based and Graph-Based Priors for Group Testing
论文作者
论文摘要
小组测试问题的目的是使用适当设计的测试来确定一组有缺陷的项目，其结果表明是否存在任何有缺陷的项目。在本文中，我们研究如何通过合并事先信息来利用项目之间的结构依赖性来显着减少测试的数量。为此，我们追求两种不同的观点：（i）作为统一组合之前的概括，我们认为有缺陷的集合在给定尺寸的所有可能集合的\ emph {subset}上是均匀的，并研究这如何影响信息理论的限制，以实现近似恢复的测试数量； （ii）作为I.I.D.〜先验的概括，我们基于ISING模型引入了一类新的先验，其中关联的图代表项目之间的相互作用。我们表明，这自然会导致整数二次程序解码器，该解码器可以转换为整数线性程序和/或放松到非整数变体，以提高计算复杂性，同时保持强大的经验恢复性能。
The goal of the group testing problem is to identify a set of defective items within a larger set of items, using suitably-designed tests whose outcomes indicate whether any defective item is present. In this paper, we study how the number of tests can be significantly decreased by leveraging the structural dependencies between the items, i.e., by incorporating prior information. To do so, we pursue two different perspectives: (i) As a generalization of the uniform combinatorial prior, we consider the case that the defective set is uniform over a \emph{subset} of all possible sets of a given size, and study how this impacts the information-theoretic limits on the number of tests for approximate recovery; (ii) As a generalization of the i.i.d.~prior, we introduce a new class of priors based on the Ising model, where the associated graph represents interactions between items. We show that this naturally leads to an Integer Quadratic Program decoder, which can be converted to an Integer Linear Program and/or relaxed to a non-integer variant for improved computational complexity, while maintaining strong empirical recovery performance.
