Universality in iterative algorithms and polytope phase transitions

Stochastic Analysis Seminar Series

We consider a class of nonlinear mappings $\F_{A,N}$ in $\mathbb{R}^N$ indexed by symmetric  random matrices  $A\in\mathbb{B}^{N\times N}$ with independent entries. Within spin glass theory, special cases of these mappings correspond to iterating the TAP equations as studied by Erwin Bolthausen. Within information theory, they are in correspondence with 'approximate  message passing' algorithms.

We study the high-dimensional (large $N$) behaviour of the iterates of $\F$, and prove that it is universal, i.e. it depends only on the first two moments of the entries of $A$, under suitable tail conditions. 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.

A joint work with M. Bayati and A. Montanari


Marc Lelarge (ENS)

Monday, January 30, 2012 - 15:45
to 16:45