  For the additive white Gaussian noise channel with average codeword power
constraint, new coding methods are devised in which the codewords are sparse
superpositions, that is, linear combinations of subsets of vectors from a given
design, with the possible messages indexed by the choice of subset. Decoding is
by least squares, tailored to the assumed form of linear combination.
Communication is shown to be reliable with error probability exponentially
small for all rates up to the Shannon capacity.
