...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Efficient Algorithms for Noisy Group Testing
【24h】

Efficient Algorithms for Noisy Group Testing

机译：噪声群测试的高效算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a “small” number of “pooled” tests (i.e., tests that have a positive outcome if at least one of the items being tested in the pool is defective, else have a negative outcome). For ease of presentation in this paper, we focus on the regime when D = O(N1-δ) for some δ > 0. The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of the literature demonstrates that θ(D log(N)) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexities that are sub-linear in N have started being investigated. In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity (O (D log(N)) in both the performance metrics). The total number of stages of our adaptive algorithm is “small” (O (log(D))). Similarly, in the scenario with nonadaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires O (D log(D) log(N)) tests and has a decoding complexity of O(D(log N +log2 D)). Finally, we present an adaptive algorithm that only requires two stages, and for which both the number of tests and the decoding complexity scale as O(D(log N +log2 D)). For all three settings, the probability of error of our algorithms scales as O (1/(poly(D)). For each of the statements mentioned earlier about the order of the number of measurements, decoding complexity, and probability of error, we provide explicitly computed “small” universal factors in our theorem statements.
机译：分组测试是指通过“少量”的“合并”测试（即，具有阳性结果的测试）从（大型）N个项目集中识别（小的）D缺陷的子集的问题。如果池中至少有一项测试项目存在缺陷，则结果为否）。为了便于本文介绍，我们将重点关注当δ> 0时D = O（N1-δ）时的情况。测试可能无噪声或有噪声，并且测试过程可能是自适应的（定义测试的库可能取决于先前测试的结果）或非自适应（每个测试的执行均独立于其他测试的结果）。大量文献证明，θ（D log（N））测试对于组测试问题在信息理论上是必要的，并且是足够的，并提供了实现此性能的算法。但是，直到最近，才开始研究具有在N中为次线性的计算复杂度的重建算法。在具有嘈杂结果的自适应测试的情况下，我们提出了第一种方案，该方案在测试数量和解码复杂度（O（D log（N）））上均同时达到阶次最优（最大为小常数因子）。性能指标）。我们的自适应算法的总阶段数为“小”（O（log（D）））。类似地，在具有嘈杂结果的非自适应测试的情况下，我们提出了在测试数量和解码复杂度上同时接近最佳的第一种方案（通过要求O（D log（D）log（N）的算法） ）测试并具有O（D（log N + log2 D））的解码复杂度。最后，我们提出了一种仅需要两个阶段的自适应算法，对于该算法，测试次数和解码复杂度均按O（D （log N + log2 D））。对于所有这三种设置，我们算法的错误概率均缩放为O（1 /（poly（D））。对于前面提到的有关测量次数顺序的每条陈述，解码复杂度和错误概率，我们在定理语句中提供了显式计算的“小”通用因子。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号