• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
【24h】

Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing

机译：通过空间耦合和近似消息传递的信息理论上的最佳压缩感知

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala [30], message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of nonzero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate $delta$ exceeds the (upper) Rényi information dimension of the signal, $overline{d}(p_{X})$. More precisely, for a sequence of signals of diverging dimension $n$ whose empirical distribution converges to $p_{X}$ , reconstruction is with high probability successful from $overline{d}(p_{X}), n+o(n)$ measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension $n$ and $k(n)$ nonzero entries, this implies reconstruction from $k(n)+o(n)$ measurements. For “discrete” signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from $o(n)$ measurements. The result is robust with respect to noise, does not apply uniquely to random signals- but requires the knowledge of the empirical distribution of the signal $p_{X}$ .
机译：我们研究了广泛的随机带状对角线感知矩阵的压缩感知重建问题。这种构造受到编码理论中空间耦合思想的启发。正如Krzakala [30]启发式地和数字地证明的那样，消息传递算法可以有效地解决欠采样率接近非零坐标分数的空间耦合测量的重构问题。我们使用近似消息传递（AMP）算法，并通过状态演化方法对其进行分析。我们给出严格的证明，一旦欠采样率$ delta $超过信号的（上）Rényi信息维$ overline {d}（p_ {X}）$，此方法便会成功。更精确地，对于经验分布收敛到$ p_ {X} $的发散维数为$ n $的信号序列，重建很有可能成功地从$ overline {d}（p_ {X}），n + o（n ）$根据带对角线矩阵进行的测量。对于稀疏信号，即维度为$ n $和$ k（n）$非零项的序列，这意味着从$ k（n）+ o（n）$测量中重建。对于“离散”信号，即，其坐标采用固定的有限值集的信号，这意味着从$ o（n）$测量值进行重构。该结果相对于噪声是鲁棒的，不是唯一地应用于随机信号，而是需要知道信号$ p_ {X} $的经验分布。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号