Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DecoderSimilar Papers 제목 키워드 기반
Graph Embeddings via Tensor Products and Approximately Orthonormal Codes
We propose a dynamic graph representation method, showcasing its rich representational capacity and establishing some of its theoretical properties. Our representation falls under the bind-and-sum approach in hyperdimens…
Compressed Computation under $L^4$ Loss is likely Computation in Superposition
Neural networks are thought to represent concepts as directions in their activation space, and superposition lets them encode more concepts than they have dimensions. It is natural to ask whether they can also compute mo…
Superposition as Lossy Compression: Measure with Sparse Autoencoders and Connect to Adversarial Vulnerability
Neural networks achieve remarkable performance through superposition: encoding multiple features as overlapping directions in activation space rather than dedicating individual neurons to each feature. This challenges in…
Adversarial RobustnessA sparse code increases the speed and efficiency of neuro-dynamic programming for optimal control tasks with correlated inputs
Sparse codes in neuroscience have been suggested to offer certain computational advantages over other neural representations of sensory data. To explore this viewpoint, a sparse code is used to represent natural images i…
Sparsity, Superposition, and Forgetting: A Mechanistic Study of Representation Retention in Continual Learning
Continual learning (CL) systems often forget previously acquired knowledge, yet the mechanisms driving forgetting remain hard to isolate in practice because real datasets entangle many factors. We present a controlled, t…
Continual Learning