论文标题
组合组测试和稀疏的恢复方案，具有近乎最佳的解码时间
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
论文作者
论文摘要
在长期研究的组合组测试问题中，要求使用$ m \ ll n $分离的测量值检测一组$ k $有缺陷的物品。在非自适应环境中，使用最广泛的组合对象是分离和列表 - 截词矩阵，它定义了测试方案的发病率矩阵。分离矩阵允许识别确切的赤字集，而列表分离的矩阵则标识了赤字的小超集。除了组合保证外，为测量设计配备有效的解码算法通常是关键兴趣。最有效的解码器应在$ n $中以套期值的时间运行，理想情况下是$ m $ $ m $的近乎线性。 在这项工作中，我们为最基本的小组测试任务以及压缩感测和重型击球手文献中的中心任务提供了几种最佳测量和近乎最佳的解码时间的结构。对于许多这些任务，先前的测量 - 最佳结构需要时间二次测量数，或者在宇宙大小中的线性。 我们的大多数结果都是通过干净且新颖的方法获得的，该方法避免了可恢复列表的代码或相关的复杂技术，这些代码几乎在每项最新的有关此类物体可有效解释的构造的最新工作中都存在。
In the long-studied problem of combinatorial group testing, one is asked to detect a set of $k$ defective items out of a population of size $n$, using $m \ll n$ disjunctive measurements. In the non-adaptive setting, the most widely used combinatorial objects are disjunct and list-disjunct matrices, which define incidence matrices of test schemes. Disjunct matrices allow the identification of the exact set of defectives, whereas list disjunct matrices identify a small superset of the defectives. Apart from the combinatorial guarantees, it is often of key interest to equip measurement designs with efficient decoding algorithms. The most efficient decoders should run in sublinear time in $n$, and ideally near-linear in the number of measurements $m$. In this work, we give several constructions with an optimal number of measurements and near-optimal decoding time for the most fundamental group testing tasks, as well as for central tasks in the compressed sensing and heavy hitters literature. For many of those tasks, the previous measurement-optimal constructions needed time either quadratic in the number of measurements or linear in the universe size. Most of our results are obtained via a clean and novel approach which avoids list-recoverable codes or related complex techniques which were present in almost every state-of-the-art work on efficiently decodable constructions of such objects.
