• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Performance of Group Testing Algorithms With Near-Constant Tests Per Item
【24h】

Performance of Group Testing Algorithms With Near-Constant Tests Per Item

机译：每项具有近乎恒定测试的分组测试算法的性能

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

摘要

We consider the nonadaptive group testing with N items, of which K = Theta (N-theta) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for theta > 0.43 and the best proven performance with a practical decoding algorithm for all theta is an element of(0, 1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when theta > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.
机译：我们考虑了N个项目的非自适应小组测试，其中K = Theta（N-theta）有缺陷。我们研究了一种测试设计，其中每个项目出现在几乎相同数量的测试中。对于每个项目，我们独立地随机选择替换均匀的L个测试，并将其放入这些测试中。我们在稀疏性范围内使用简单实用的解码算法分析了这些设计的性能，并表明与标准伯努利设计相比，性能得到了持续改善。我们证明，当与称为组合正交匹配追踪和确定缺陷（DD）的简单解码算法搭配使用时，我们的新设计比Bernoulli设计所需的测试少大约23％。这给出了theta> 0.43的最著名的非自适应组测试性能，而对于所有theta的实用解码算法的最可靠的性能证明是（0，1）的元素。我们还给出了相反的结果，表明当theta> 1/2时，相对于我们的随机设计，DD算法是最佳的。我们通过仿真对理论结果进行补充，这些仿真表明在稀疏和密集状态下，Bernoulli设计都有显着改进。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号