• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Nearly Optimal Sparse Group Testing
【24h】

Nearly Optimal Sparse Group Testing

机译：几乎最佳的稀疏组测试

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

摘要

Group testing is the process of pooling arbitrary subsets from a set of n items so as to identify, with a minimal number of tests, a "small" subset of d defective items. In "classical" non-adaptive group testing, it is known that when d is substantially smaller than n, Theta(d log(n)) tests are both information-theoretically necessary and sufficient to guarantee recovery with high probability. Group testing schemes in the literature that meet this bound require most items to be tested Omega(log(n)) times, and most tests to incorporate Omega(n/d) items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be "sparse." Specifically, we consider (separately) scenarios in which 1) items are finitely divisible and hence may participate in at most gamma is an element of o(log(n)) tests; or 2) tests are size-constrained to pool no more than rho is an element of o(n/d) items per test. For both scenarios, we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In particular, one of our main results shows that gamma-finite divisibility of items forces any non-adaptive group testing algorithm with the probability of recovery error at most is an element of to perform at least gamma d(n/d)((1-5 is an element of)/gamma) tests. Analogously, for rho-sized constrained tests, we show an information-theoretic lower bound of Omega(n/rho) tests for high-probability recovery-hence in both settings the number of tests required grows dramatically (relative to the classical setting) as a function of n. In both scenarios, we provide both randomized constructions and explicit constructions of designs with computationally efficient reconstruction algorithms that require a number of tests that is optimal up to constant or small polynomial factors in some regimes of n, d, gamma, and rho. The randomized design/reconstruction algorithm in the rho-sized test scenario is universal-independent of the value of d, as long as rho is an element of o(n/d). We also investigate the effect of unreliabilityoise in test outcomes, and show that whereas the impact of noise in test outcomes can be obviated with a small (constant factor) penalty in the number of tests in the rho-sized tests scenario, there is no group-testing procedure, regardless of the number of tests, that can combat noise in the gamma-divisible scenario.
机译：组测试是从一组N项汇集任意子集的过程，以便识别，具有最小的测试数，D缺陷物品的“小”子集。在“经典”非自适应组测试中，众所周知，当D基本上小于n时，THETA（D log（n））测试是信息 - 理论上是必要的，并且足以保证具有高概率的高概率。符合此绑定的文献中的组测试方案需要大多数要测试的项目ω（n））次，以及包含omega（n / d）项目的大多数测试。通过物理考虑，我们研究了测试程序的组测试模型，其中测试程序被约束为“稀疏”。具体地，我们考虑（单独）方案，其中1）物品有限可分隔，因此可以参与大多数伽玛是O（log（n））测试的元素;或2）测试的尺寸约束池不超过rho是每个测试的O（n / d）项目的元素。对于这两种情况，我们提供了保证高概率恢复所需的测试数量的信息 - 理论下限。特别是，我们的主要结果之一表明，物品的伽马有限可分配性强制任何非自适应组测试算法最多恢复误差的概率是至少伽马D（n / d）的元素（（1 -5是）/γ）测试的元素。类似地，对于Rho大小的受限测试，我们显示了ω（n / rho）测试的信息 - 理论下限，用于高概率恢复的测试 - 因此，在两个设置中，所需的测试数量大幅增加（相对于经典设置） n的函数。在这两种情况下，我们提供随机结构和具有计算有效的重建算法的设计和明确的结构，该算法需要许多测试，该算法在N，D，伽马和rho的一些制度中最佳地最佳或小多项式因子。随机设计/重建算法在RHO大小的测试场景中是普遍无关的D值，只要rho是O（n / d）的元素。我们还调查了测试结果中不可靠性/噪音的影响，并且表明，在RHO大小测试场景中的测试数量中，可以通过小（恒定因素）罚款来避免测试结果中的噪音的影响。无论测试的数量如何，无群体测试程序，可以打击伽马可分地区情景中的噪声。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号