Novel Impossibility Results for Group-Testing
Novel Impossibility Results for Group-Testing
复制标题
小组测试的新不可能结果
DOI：
10.1109/isit.2018.8437471
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Arya Mazumdar
中科院分区：
文献类型：
--
作者：
Abhishek Agarwal;S. Jaggi;Arya Mazumdar
在这项工作中，我们通过Madiman-Tetali不等式证明了也许是最简单的非线性估计问题（分组测试（GT））的新不可能结果。分组测试关注的是通过t$分离测量从n$个项目中识别出d$个缺陷项目。我们考虑线性稀疏性机制，即对于任何常数$\delta > 0$，$d=\delta n$，这是迄今为止很少探索的（尽管是自然的）机制。在一个标准的信息论设置中，要求测试是非自适应的，并且允许小概率的重建错误，我们的$t$的下限是第一个改进经典计数下限的，$t/n\geq H（\delta）$，其中$H（\cdot）$是二进制熵函数。作为我们结果的推论，我们表明：（i）对于$\delta \gtrsim 0.347$，个体测试本质上是最优的，即，$t\geq n（1-o（1））$;和（ii）有一个自适应差距，因为对于$\delta\in$（0.3471，0.3819）已知的自适应GT算法需要少于$n$测试来重建$\mathcal{D}$，而我们的界限意味着最好的非自适应算法必须基本上是每个元素的单独测试。也许最重要的是，我们的工作提供了一个框架，组合和信息理论的方法来推导各种非线性估计问题的下限。
In this work we prove new impossibility results for perhaps the simplest non-linear estimation problem, that of Group Testing (GT), via the Madiman-Tetali inequalities. Group Testing concerns itself with identifying $d$ defective items from a set of $n$ items via $t$ disjunctive measurements. We consider the linear sparsity regime, i.e. $d=\delta n$ for any constant $\delta > 0$, a hitherto little-explored (though natural) regime. In a standard information-theoretic setting, where the tests are required to be non-adaptive and a small probability of reconstruction error is allowed, our lower bounds on $t$ are the first that improve over the classical counting lower bound, $t/n\geq H(\delta)$, where $H(\cdot)$ is the binary entropy function. As corollaries of our result, we show that (i) for $\delta \gtrsim 0.347$, individual testing is essentially optimal, i.e., $t\geq n(1-o(1))$; and (ii) there is an adaptivity gap, since for $\delta\in$ (0.3471,0.3819) known adaptive GT algorithms require fewer than $n$ tests to reconstruct $\mathcal{D}$, whereas our bounds imply that the best nonadaptive algorithm must essentially be individual testing of each element. Perhaps most importantly, our work provides a framework for combining combinatorial and information-theoretic methods for deriving lower bounds for a variety of non-linear estimation problems.