  We study the behavior of Approximate Message-Passing, 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 Approximate Message-Passing decoder to
perform at large rates for moderate block length.
