Statistical Estimation on Graphs

on YouTube ↗31m

" summary

Random LDPC code (rate 1/2, degree 3/6) shows a sharp gap between the local decoder threshold (belief propagation) and the information-theoretic threshold (MAP); spatial coupling provably pushes BP up to MAP so a polynomial local algorithm hits capacity. Dense compressed sensing uses approximate message passing (iterate A^T times residual + nonlinear denoiser); soft-threshold AMP matches L1 phase transitions, with a recover/no-recover boundary (example: ε=0.2 gives δ≈0.2). Spiked tensor models show a diverging computational gap: information-theoretic SNR ~1 but known algorithms require SNR scaling like N^{k/4} (local ones N^{k/2}).

AI-written summary · about

" chapters (6)

1. 0:00Introduction to coding theory
2. 7:05Phase transitions in decoding
3. 14:19Compressed sensing analysis
4. 19:48Sparse coding and tensors
5. 23:25Tensor reconstruction problems
6. 27:11Q&A and concluding remarks

" related talks

• 48mSpatial Coupling as a Proof TechniqueNicolas Macris · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013
• 38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix EstimationCynthia Rush · Rigorous Evidence for Information-Computation Trade-offs
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement ProcessesSidharth Jaggi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs