Paper Info
Title
Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements
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.
Year
DOI
Venue
2017
10.1109/TIT.2019.2947058
IEEE Transactions on Information Theory
Keywords
DocType
Volume
Approximation algorithms,Convergence,Measurement units,Heuristic algorithms,Matrix decomposition,Estimation error,Physics
Journal
66
Issue
ISSN
Citations 
1
0018-9448
13
PageRank 
References 
Authors
0.58
19
1
Name
Order
Citations
PageRank
Keigo Takeuchi19312.11