Limits on Support Recovery With Probabilistic Models: An Information-Theoretic Framework
Limits on Support Recovery With Probabilistic Models: An Information-Theoretic Framework
复制标题
概率模型支持恢复的限制：信息理论框架
DOI：
--
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
V. Cevher
中科院分区：
文献类型：
--
作者：
J. Scarlett;V. Cevher
支持恢复问题包括确定一组变量的稀疏子集，该变量与生成一组观测值相关，并且在各种设置中出现，例如压缩感知，回归中的子集选择和组测试。在本文中，我们采取统一的方法来支持恢复问题，考虑一般的概率模型相关的稀疏数据向量的观测向量。我们研究了信息理论的限制，精确和部分支持恢复，采取一种新的方法，激励阈值技术在信道编码。我们提供了一般的可扩展性和匡威界之间的权衡的错误概率和测量的数量，我们专门这些线性，1位，和组测试模型。在几种情况下，我们的边界不仅提供了匹配的缩放律在必要和足够的数量的测量，但也尖锐的阈值匹配常数因子。我们的方法比以前的方法有几个优点。对于可扩展性部分，我们在稀疏水平和其他参数的更宽尺度下获得尖锐的阈值（例如，信噪比），而对于匡威部分，我们不仅给出了错误概率不为零的条件，而且给出了错误概率趋于1的条件.
The support recovery problem consists of determining a sparse subset of a set of variables that is relevant in generating a set of observations, and arises in a diverse range of settings, such as compressive sensing, subset selection in regression, and group testing. In this paper, we take a unified approach to support recovery problems, considering general probabilistic models relating a sparse data vector to an observation vector. We study the information-theoretic limits of both exact and partial support recovery, taking a novel approach motivated by thresholding techniques in channel coding. We provide general achievability and converse bounds characterizing the trade-off between the error probability and number of measurements, and we specialize these to the linear, 1-bit, and group testing models. In several cases, our bounds not only provide matching scaling laws in the necessary and sufficient number of measurements, but also sharp thresholds with matching constant factors. Our approach has several advantages over previous approaches. For the achievability part, we obtain sharp thresholds under broader scalings of the sparsity level and other parameters (e.g., signal-to-noise ratio) compared with several previous works, and for the converse part, we not only provide conditions under which the error probability fails to vanish, but also conditions under which it tends to one.
影响因子：
1.6
作者：
Amelunxen, Dennis;Lotz, Martin;Tropp, Joel A.
通讯作者：
Tropp, Joel A.