UNIVERSALITY IN POLYTOPE PHASE TRANSITIONS AND MESSAGE PASSING ALGORITHMS

• 成果类型: Article
• 署名作者: Bayati, Mohsen; Lelarge, Marc; Montanari, Andrea
• 署名单位: Stanford University; Inria; Universite PSL; Ecole Normale Superieure (ENS); Stanford University; Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/14-AAP1010
• 发表日期: 2015
• 页码: 753-822
• 关键词: neighborliness; EQUATIONS

摘要

We consider a class of nonlinear mappings F-A,F-N in R-N indexed by symmetric random matrices A is an element of R-NxN with independent entries. Within spin glass theory, special cases of these mappings correspond to iterating the TAP equations and were studied by Bolthausen [Comm. Math. Phys. 325 (2014) 333-366]. Within information theory, they are known as approximate message passing algorithms. We study the high-dimensional (large N) behavior of the iterates of F for polynomial functions F, and prove that it is universal; that is, it depends only on the first two moments of the entries of A, under a sub-Gaussian tail condition. As an application, we prove the universality of a certain phase transition arising in polytope geometry and compressed sensing. This solves, for a broad class of random projections, a conjecture by David Donoho and Jared Tanner.