Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements

DOI10.1109/TIT.2019.2947058MaRDI QIDQ5211606zbMATH OpenOpenAlexFDO

Authors Keigo Takeuchi

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05284

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Strong limit theorems (60F15) Bayesian inference (62F15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. The main result is the justification of state evolution (SE) equations conjectured by Ma and Ping. This result implies that the EP-based algorithm achieves the Bayes-optimal performance that was originally derived via a non-rigorous tool in statistical physics and proved partially in a recent paper, when the compression rate is larger than a threshold. The proof is based on an extension of a conventional conditioning technique for the standard Gaussian matrix to the case of the Haar matrix.

Cited in

(6)

• Consistency of \(\ell_1\) recovery from noisy deterministic measurements
• Analysis of random sequential message passing algorithms for approximate inference
• A dynamical mean-field theory for learning in restricted Boltzmann machines
• A Unifying Tutorial on Approximate Message Passing
• Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
• Spectrum-aware debiasing: a modern inference framework with applications to principal components regression

This page was built for publication: Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211606)