Fast Sparse Superposition Codes: Communication by Regression

Wednesday, February 20, 2013
6:00 PM
Free and open to the public

A solution is presented to the problem of provable, fast, reliable, capacity-achieving communications for the additive Gaussian noise channel. This is an important real communications problem for which the fundamental limits of reliability were initially established in the capacity theorem of Shannon in 1948. Not till the 1990s were practical high-rate schemes developed and these form an essential part of the cell phone revolution. However, the demonstration of their reliability is only empirical. The codes we develop here are sparse superposition codes based on a high-dimensional regression model, and they have fast encoders and decoders based on iterative regression fits. In this presentation we describe the framework permitting theoretical demonstration of the desired properties. The error probability is shown to scale favorably with the size of the code, namely, the error probability is exponentially small for every fixed communication rate below capacity. Remaining challenges are discussed in understanding how the complexity scales when the rate approaches capacity. This work is joint with Antony Joseph and Sanghee Cho.

x x


Andrew Barron

Yale University