Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

作者：Barbier Jean^*; Schuelke Christophe; Krzakala Florent

来源：Journal of Statistical Mechanics: Theory and Experiment , 2015, 2015(5): P05013.

DOI：10.1088/1742-5468/2015/05/P05013

• message-passing algorithms
• error-correcting codes
• statistical inference

We study the behavior of approximate message-passing (AMP), a solver for linear sparse estimation problems such as compressed sensing, when the i.i.d matrices-for which it has been specifically designed-are replaced by structured operators, such as Fourier and Hadamard ones. We show empirically that after proper randomization, the structure of the operators does not significantly affect the performances of the solver. Furthermore, for some specially designed spatially coupled operators, this allows a computationally fast and memory efficient reconstruction in compressed sensing up to the information-theoretical limit. We also show how this approach can be applied to sparse superposition codes, allowing the AMP decoder to perform at large rates for moderate block length.

• 出版日期2015-5