期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 59, 期 11, 页码 7434-7464出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2013.2274513
关键词
Approximate message passing; compressed sensing; information dimension; spatial coupling; state evolution
资金
- NSF CAREER award [CCF-0743978]
- NSF [DMS-0806211]
- AFOSR [FA9550-10-1-0360]
- Caroline and Fabian Pease Stanford Graduate Fellowship
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 et al. [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) Renyi information dimension of the signal, (d) over bar (px). More precisely, for a sequence of signals of diverging dimension n whose empirical distribution converges to px, reconstruction is with high probability successful from (d) over bar (px) 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 px.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据