Universality in iterative algorithms and polytope phase transitions

Monday 30th January 2012 – 15:45 to 16:45

Speaker: Marc Lelarge (ENS)

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.

Part of the Stochastic Analysis Seminar Series