Technical Program

Paper Detail

Paper IDL.8.2
Paper Title Exponentially Fast Concentration of Vector Approximate Message Passing to its State Evolution
Authors Collin Cademartori, Cynthia Rush, Columbia University, United States
Session L.8: Learning and Message-Passing
Presentation Lecture
Track Statistics and Learning Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Vector Approximate Message Passing is a computationally-efficient iterative algorithm for estimation in high-dimensional regression problems. Due to the presence of an ‘Onsager’ correction term in its iterates, for a wide class of N by M design matrices, namely those that are right orthogonally-invariant, the asymptotic distribution of the algorithm’s estimate of the signal at any iteration can be exactly characterized in the large system limit as M/N → δ ∈ (0,∞) via a scalar recursion referred to as state evolution. In this paper, we show that appropriate functionals of the iterates in fact concentrate around their limiting values predicted by these asymptotic distributions with rates exponentially fast in N.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!