Nonadaptive Group Testing With Random Set of Defectives
Nonadaptive Group Testing With Random Set of Defectives
复制标题
使用随机缺陷集进行非自适应分组测试
DOI：
10.1109/tit.2016.2613870
复制
发表时间：
2015
影响因子：
2.5
通讯作者：
A. Mazumdar
中科院分区：
文献类型：
--
作者：
A. Mazumdar
在分组测试方案中，设计了一系列测试来识别大量 N 个项目中存在的少量 t 个缺陷项目。每个测试都将一组物品作为输入，并产生一个二进制输出，指示该组中是否存在任何有缺陷的物品。在非自适应方案中，测试必须一次性设计。在这种情况下，设计一个测试方案相当于构造一个析取矩阵，一个 M × N 的二元矩阵，其中任何 t 列的支持集的并集不包含任何其他列的支持集。原则上，我们希望拥有这样一个行数最少为 M 的矩阵。在本文中，我们考虑缺陷品是随机的并遵循简单概率分布的情况。特别是，我们考虑以下情况：1）每个项目都可以独立地以 t/N 的概率存在缺陷，2）每个 t 组项目可以以均匀的概率存在缺陷。在这两种情况下，我们的目标是设计一个测试矩阵，以高概率成功识别一组缺陷品。这两种模型之前都在文献中进行过研究，并且众所周知，在这两种情况下， θ(t log N) 测试都是必要且充分的（通过随机编码）。我们的主要重点是适合上述场景的测试矩阵的显式确定性构造。构造测试矩阵的最流行的方法之一依赖于恒权纠错码及其最小距离。特别是，众所周知，代码会产生具有 O(t2 log N) 行的测试矩阵，用于识别任何 t 个缺陷。我们超越了最小距离分析，并将恒定权重代码的平均距离连接到结果测试矩阵的参数。事实上，我们展示了距离（矩阵列的成对属性）如何转换为列的 (t + 1) 属性。通过我们宽松的要求，我们表明，使用显式常量代码（例如，基于代数几何代码），我们可以为第一种情况和第二种情况实现等于 O(t(log2 N/log t)) 的测试数量。虽然与最佳测试数量仅相差 (log N/log t) 一个因素，但这是可以从确定性构造中获得的最佳参数集，我们的主要贡献在于将组测试属性与恒定权重代码的平均和最小距离相关联。
In a group testing scheme, a series of tests are designed to identify a small number t of defective items that are present among a large number N of items. Each test takes a group of items as input and produces a binary output indicating whether any defective item is present in the group. In a nonadaptive scheme, the tests have to be designed in one-shot. In this setting, designing a testing scheme is equivalent to the construction of a disjunct matrix, an M × N binary matrix where the union of supports of any t columns does not contain the support of any other column. In principle, one wants to have such a matrix with a minimum possible number M of rows. In this paper, we consider the scenario where defective items are random and follow simple probability distributions. In particular, we consider the cases where: 1) each item can be defective independently with probability t/N and 2) each t-set of items can be defective with uniform probability. In both the cases, our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before, and it is known that Θ(t log N) tests are necessary as well as sufficient (via random coding) in both the cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on constant-weight error-correcting codes and their minimum distance. In particular, it is known that codes result in test matrices with O(t2 log N) rows that identify any t defectives. We go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of the resulting test matrix. Indeed, we show how distance, a pairwise property of the columns of the matrix, translates to a (t + 1)-wise property of the columns. With our relaxed requirements, we show that using explicit constant-weight codes (e.g., based on algebraic geometry codes) we may achieve a number of tests equal to O(t(log2 N/log t)) for both the first and second cases. While only away by a factor of (log N/log t) from the optimal number of tests, this is the best set of parameters that one can obtain from a deterministic construction, and our main contribution lies in relating the group testing properties to the average and minimum distances of constant-weight codes.
影响因子：
0.9
作者：
Wahba, Grace
通讯作者：
Wahba, Grace