Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes. (18th May 2015)

• Record Type: Journal Article
• Authors: Barbier, Jean; Schülke, Christophe; Krzakala, Florent
• Is Part Of: Journal of statistical mechanics. (2015:May)
• Publication Date: 2015-05-18
• Subjects: 11; 11/050 -- 11/018 -- 11/105; Statistical mechanics -- Periodicals; Mechanics -- Statistical methods -- Periodicals; 530.1305
• DOI: 10.1088/1742-5468/2015/05/P05013
• Languages: English
• ISSNs: 1742-5468

Abstract

Abstract: 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.