  Sparse superposition codes were recently introduced by Barron and Joseph for
reliable communication over the AWGN channel at rates approaching the channel
capacity. The codebook is defined in terms of a Gaussian design matrix, and
codewords are sparse linear combinations of columns of the matrix. In this
paper, we propose an approximate message passing decoder for sparse
superposition codes, whose decoding complexity scales linearly with the size of
the design matrix. The performance of the decoder is rigorously analyzed and it
is shown to asymptotically achieve the AWGN capacity with an appropriate power
allocation. Simulation results are provided to demonstrate the performance of
the decoder at finite blocklengths. We introduce a power allocation scheme to
improve the empirical performance, and demonstrate how the decoding complexity
can be significantly reduced by using Hadamard design matrices.
