It Was “All” for “Nothing”: Sharp Phase Transitions for Noiseless Discrete Channels
It Was “All” for “Nothing”: Sharp Phase Transitions for Noiseless Discrete Channels
复制标题
DOI：
10.1109/tit.2022.3225802
复制
发表时间：
2021-02
影响因子：
2.5
通讯作者：
Jonathan Niles-Weed;Ilias Zadik
中科院分区：
文献类型：
--
作者：
Jonathan Niles-Weed;Ilias Zadik
对于无噪声的离散信道，我们建立了一种称为“全有或全无”现象的相变。这类模型包括伯努利群体测试模型和种植高斯感知器模型。以前，这类模型是否存在全有或全无现象仅在有限的参数范围内为人所知。我们的工作将结果推广到所有具有任意次线性稀疏性的信号。在过去的几年里，作为两个看似互不相交的结果的结果，有或有或无的现象在不同的模型中得到了确立：一个积极的结果建立了全有或全无的一半，一个不可能的结果建立了“无”的一半。我们在本工作中的主要技术是证明，对于无噪声的离散信道，“全部”的一半意味着“没有”的一半，即“全部”的证明可以变成“没有”的证明。由于“全部”的一半通常可以通过直接的方法来证明--例如，通过第一矩方法--我们的等价性为在其他情况下确定这一现象的存在提供了一种强大而普遍的方法。
We establish a phase transition known as the “all-or-nothing” phenomenon for noiseless discrete channels. This class of models includes the Bernoulli group testing model and the planted Gaussian perceptron model. Previously, the existence of the all-or-nothing phenomenon for such models was only known in a limited range of parameters. Our work extends the results to all signals with arbitrary sublinear sparsity. Over the past several years, the all-or-nothing phenomenon has been established in various models as an outcome of two seemingly disjoint results: one positive result establishing the “all” half of all-or-nothing, and one impossibility result establishing the “nothing” half. Our main technique in the present work is to show that for noiseless discrete channels, the “all” half implies the “nothing” half, that is, a proof of “all” can be turned into a proof of “nothing.” Since the “all” half can often be proven by straightforward means—for instance, by the first-moment method—our equivalence gives a powerful and general approach towards establishing the existence of this phenomenon in other contexts.