Statistical and Computational Phase Transitions in Group Testing
Statistical and Computational Phase Transitions in Group Testing
复制标题
分组测试中的统计和计算相变
DOI：
10.48550/arxiv.2206.07640
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ilias Zadik
中科院分区：
文献类型：
--
作者：
A. Coja;Oliver Gebhard;Max Hahn;Alexander S. Wein;Ilias Zadik
我们研究的组测试问题，其目标是确定一组k个感染的个人携带一种罕见的疾病，在一个人口规模为n，根据汇总测试的结果，返回阳性时，至少有一个感染的个人在测试组。我们考虑两种不同的简单随机程序分配个人的测试：常数列设计和伯努利设计。我们的第一组结果涉及基本的统计极限。对于恒列设计，我们给出了一个新的信息理论下限，这意味着正确识别的感染个体的比例经历了一个尖锐的“全有或全无”的相变时，测试的数量超过一个特定的阈值。对于伯努利设计，我们确定了解决相关检测问题所需的精确测试数量（目标是区分组测试实例和纯噪声），改进了Truong，阿尔德里奇和Scarlett（2020）的上限和下限。对于这两个组测试模型，我们还研究了计算效率（多项式时间）的推理程序的权力。我们确定的精确数量的测试所需的类的低次多项式算法来解决检测问题。这提供了一个内在的计算统计差距在小稀疏水平的检测和恢复问题的证据。值得注意的是，我们的证据与Iliopoulos和Zadik（2021）的相反，他们预测伯努利设计中不存在计算统计差距。
We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on the outcomes of pooled tests which return positive whenever there is at least one infected individual in the tested group. We consider two different simple random procedures for assigning individuals to tests: the constant-column design and Bernoulli design. Our first set of results concerns the fundamental statistical limits. For the constant-column design, we give a new information-theoretic lower bound which implies that the proportion of correctly identifiable infected individuals undergoes a sharp"all-or-nothing"phase transition when the number of tests crosses a particular threshold. For the Bernoulli design, we determine the precise number of tests required to solve the associated detection problem (where the goal is to distinguish between a group testing instance and pure noise), improving both the upper and lower bounds of Truong, Aldridge, and Scarlett (2020). For both group testing models, we also study the power of computationally efficient (polynomial-time) inference procedures. We determine the precise number of tests required for the class of low-degree polynomial algorithms to solve the detection problem. This provides evidence for an inherent computational-statistical gap in both the detection and recovery problems at small sparsity levels. Notably, our evidence is contrary to that of Iliopoulos and Zadik (2021), who predicted the absence of a computational-statistical gap in the Bernoulli design.
登录
查看更多内容
DOI：
--
发表时间：
2020-05
期刊：
--
影响因子：
--
作者：
Matthew Brennan;Guy Bresler
通讯作者：
Matthew Brennan;Guy Bresler
影响因子：
3.5
作者：
ARRATIA, R;GORDON, L
通讯作者：
GORDON, L
影响因子：
2.5
作者：
Wu, Yihong;Xu, Jiaming;Yu, Sophie H.
通讯作者：
Yu, Sophie H.
影响因子：
2.5
作者：
Jonathan Niles-Weed;Ilias Zadik
通讯作者：
Jonathan Niles-Weed;Ilias Zadik
稀疏尖峰矩阵估计中的全有或全无统计和计算相变
DOI：
--
发表时间：
2020
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Barbier, J;Macris, N;Rush, C
通讯作者：
Rush, C