Group Testing in the High Dilution Regime
Group Testing in the High Dilution Regime
复制标题
高稀释状态下的团体测试
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
A. Bandeira
中科院分区：
文献类型：
--
作者：
Gabriel Arpino;Nicolò Grometto;A. Bandeira
非自适应组测试是指使用最少数量的同时池测试从较大的群体中推断出稀疏的缺陷集的问题。近年来无噪音群体测试的积极结果推动了实用噪声模型的研究，其中最突出的是稀释噪声。在稀释噪声模型下，测试池中的项目被独立稀释的概率是固定的，这意味着它们对测试的贡献不生效。在这种情况下，我们研究了相对于现有算法实现错误概率消失所需的测试数量，并提供了一个与算法无关的逆界。与其他噪声模型相比，我们还遇到了一个有趣的现象，即通过选择合适的噪声电平相关的伯努利测试设计，可以抵消所得到的测试结果的稀释噪声，从而在高噪声状态下匹配可达性和逆界。
Non-adaptive group testing refers to the problem of inferring a sparse set of defectives from a larger population using the minimum number of simultaneous pooled tests. Recent positive results for noiseless group testing have motivated the study of practical noise models, a prominent one being dilution noise. Under the dilution noise model, items in a test pool have a fixed probability of being independently diluted, meaning their contribution to a test does not take effect. In this setting, we investigate the number of tests required to achieve vanishing error probability with respect to existing algorithms and provide an algorithm-independent converse bound. In contrast to other noise models, we also encounter the interesting phenomenon that dilution noise on the resulting test outcomes can be offset by choosing a suitable noise-level-dependent Bernoulli test design, resulting in matching achievability and converse bounds up to order in the high noise regime.