We consider a class of nonlinear mappings FA, N in RN indexed by symmetric random matrices A ∊ RN×N with independent entries. Within spin glass theory, special cases of these mappings correspond to iterating the TAP equations and were studied by Erwin Bolthausen. 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, i.e. it depends only on the first two moments of the entries of A. As an application, we prove the universality of a certain phase transition arising in polytope geometry and compressed sensing. This solves a conjecture by David Donoho and Jared Tanner.
展开▼
机译：我们考虑一类由对称随机矩阵A ∊ R N×N 索引且具有独立条目的R N 中的非线性映射FA，N。在自旋玻璃理论中，这些映射的特例对应于迭代TAP方程，并由Erwin Bolthausen研究。在信息论中，它们被称为“近似消息传递”算法。我们研究多项式函数F的F的迭代的高维（大N）行为，并证明它是通用的，即，它仅取决于A项的前两个时刻。作为应用，我们证明了多位点几何形状和压缩感测中出现的特定相变的普遍性。这解决了David Donoho和Jared Tanner的一个猜想。
展开▼
