Semidefinite programs simulate approximate message passing robustly

Misha Ivkov, Tselil Schramm

Approximate message passing (AMP) is a family of iterative algorithms that generalize matrix power iteration. AMP algorithms are known to optimally solve many average-case optimiza…