2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | L.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
