State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling

Adel Javanmard; Andrea Montanari

arxiv: 1211.5164 · v2 · pith:E3V47P3Snew · submitted 2012-11-21 · 🧮 math.PR · cs.IT· math.IT· math.ST· stat.TH

State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling

Adel Javanmard , Andrea Montanari This is my paper

classification 🧮 math.PR cs.ITmath.ITmath.STstat.TH

keywords algorithmsevolutionmatricesmessagepassingproofsensingstate

0 comments

read the original abstract

We consider a class of approximated message passing (AMP) algorithms and characterize their high-dimensional behavior in terms of a suitable state evolution recursion. Our proof applies to Gaussian matrices with independent but not necessarily identically distributed entries. It covers --in particular-- the analysis of generalized AMP, introduced by Rangan, and of AMP reconstruction in compressed sensing with spatially coupled sensing matrices. The proof technique builds on the one of [BM11], while simplifying and generalizing several steps.

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

When Stronger Triggers Backfire: A High-Dimensional Theory of Backdoor Attacks
cs.LG 2026-05 unverdicted novelty 8.0

In the proportional high-dimensional regime, stronger backdoor training triggers improve clean accuracy and make attack success non-monotonic for regularized GLMs on Gaussian mixtures, with closed-form proofs for squa...