Sparse Superposition Codes for the AWGN Channel, Message Passing, Replica and Spatial Coupling

on YouTube ↗37m

" summary

Sparse superposition codes encode messages as L sections of size B with one nonzero entry, then multiply by a random or Hadamard matrix and send over AWGN; decoding uses approximate message passing (Gaussian BP + TAP approximations), analyzed by state evolution and the replica potential, which predicts an abrupt SER threshold. AMP runs in O(N^2) or O(N log N) with Hadamard; naive power allocation fails at finite sizes, but spatial coupling wave removes the BP/MAP gap and empirically yields SER < 10^-6 at rate 1.5 (B=512, block ≈5000).

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 6:02Sparse Superposition codes = Multi-dimensional estimation problem
3. 6:59Graphical model
4. 9:41From belief propagation to AMP
5. 14:44A heuristic computation of the optimal SER
6. 17:59Gap to capacity closing polynomially
7. 18:21Error floor decay polynomially with B
8. 19:17State Evolution vs AMP for finite sizes
9. 19:35State Evolution Analysis and the replica potential
10. 22:21Two ways to make AMP capacity achieving
11. 27:01Comparing everything

" related talks

• 48mSpatial Coupling as a Proof TechniqueNicolas Macris · Random Instances and Phase Transitions (Simons Institute, 2016)
• 49mApproximate Message Passing Algorithms For Orthogonally Invariant ModelsZhou Fan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022
• 01h 06mTutorial: Methods from Statistical Physics IIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 43mCoded matrix computation: numerical stability, partial stragglers and sparse input matricesAditya Ramamoorthy · Application-Driven Coding Theory 2024
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 29mAre Generative Models The New Sparsity?Bruno Loureiro · Rigorous Evidence for Information-Computation Trade-offs