Online Program Home
  My Program Register!

Abstract Details

Activity Number: 83
Type: Invited
Date/Time: Sunday, July 30, 2017 : 8:30 PM to 10:30 PM
Sponsor: IMS
Abstract #323299
Title: Approximate Message Passing Algorithms for High-Dimensional Regression
Author(s): Cynthia Rush*
Companies: Columbia University
Keywords: algorithms ; approximate message passing ; image reconstruction ; high-dimensional regression ; compressed sensing
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 high-dimensional regression, where the goal is to estimate a highdimensional vector x from an observation y = A x + w. AMP is a low-complexity, 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.


Authors who are presenting talks have a * after their name.

Back to the full JSM 2017 program

 
 
Copyright © American Statistical Association