Abstract:

This poster studies the performance of Approximate Message Passing (AMP), in the regime where the problem dimension is large but finite. We consider the setting of highdimensional regression, where the goal is to estimate a highdimensional vector x from an observation y = A x + w. AMP is a lowcomplexity, scalable algorithm for this problem. It has the attractive feature that its performance can be accurately characterized in the asymptotic large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this work, we derive a concentration result for AMP with i.i.d. Gaussian measurement matrices with finite dimension n times N. The result shows that the probability of deviation from the state evolution prediction falls exponentially in n. Our result provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions.
