On the Convergence of Orthogonal/Vector AMP: Long-Memory Message-Passing Strategy

被引：16
作者：
Takeuchi, Keigo [1 ]
机构：
[1] Toyohashi Univ Technol, Dept Elect & Elect Informat Engn, Toyohashi, Aichi 4418580, Japan
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2022年 / 68卷 / 12期
基金：
日本学术振兴会;
关键词：
Convergence; Damping; Sensors; Heuristic algorithms; Sparse matrices; Mathematical models; Compressed sensing; orthogonal; vector approximate message-passing (AMP); long memory; damping; state evolution; convergence analysis; MULTIUSER DETECTION; SIGNAL RECOVERY; STATE EVOLUTION; CDMA SYSTEMS; SPREAD CDMA; ALGORITHMS; DYNAMICS;
D O I：
10.1109/TIT.2022.3194855
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Orthogonal/vector approximate message-passing (AMP) is a powerful message-passing (MP) algorithm for signal reconstruction in compressed sensing. This paper proves the convergence of Bayes-optimal orthogonal/vector AMP in the large system limit. The proof strategy is based on a novel long-memory (LM) MP approach: A first step is a construction of LM-MP that is guaranteed to converge systematically. A second step is a large-system analysis of LM-MP via an existing framework of state evolution. A third step is to prove the convergence of state evolution recursions for Bayes-optimal LM-MP via a new statistical interpretation of existing LM damping. The last is an exact reduction of the state evolution recursions for Bayes-optimal LM-MP to those for Bayes-optimal orthogonal/vector AMP. The convergence of the state evolution recursions for Bayes-optimal LM-MP implies that for Bayes-optimal orthogonal/vector AMP. Numerical simulations are presented to show the verification of state evolution results for damped orthogonal/vector AMP and a negative aspect of LM-MP in finite-sized systems.
引用
收藏
页码：8121 / 8138
页数：18
相关论文
共 61 条
[1]   Asymptotically liberating sequences of random unitary matrices [J].
Anderson, Greg W. ;
Farrell, Brendan .
ADVANCES IN MATHEMATICS, 2014, 255 :381-413
[2]   Compressed Channel Sensing: A New Approach to Estimating Sparse Multipath Channels [J].
Bajwa, Waheed U. ;
Haupt, Jarvis ;
Sayeed, Akbar M. ;
Nowak, Robert .
PROCEEDINGS OF THE IEEE, 2010, 98 (06) :1058-1076
[3]   The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference [J].
Barbier, Jean ;
Macris, Nicolas .
PROBABILITY THEORY AND RELATED FIELDS, 2019, 174 (3-4) :1133-1185
[4]  
Barbier J, 2018, IEEE INT SYMP INFO, P1390, DOI 10.1109/ISIT.2018.8437522
[5]   UNIVERSALITY IN POLYTOPE PHASE TRANSITIONS AND MESSAGE PASSING ALGORITHMS [J].
Bayati, Mohsen ;
Lelarge, Marc ;
Montanari, Andrea .
ANNALS OF APPLIED PROBABILITY, 2015, 25 (02) :753-822
[6]   The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing [J].
Bayati, Mohsen ;
Montanari, Andrea .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (02) :764-785
[7]   State evolution for approximate message passing with non-separable functions [J].
Berthier, Raphael ;
Montanari, Andrea ;
Phan-Minh Nguyen .
INFORMATION AND INFERENCE-A JOURNAL OF THE IMA, 2020, 9 (01) :33-79
[8]  
Caltagirone F, 2014, IEEE INT SYMP INFO, P1812, DOI 10.1109/ISIT.2014.6875146
[9]   Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information [J].
Candès, EJ ;
Romberg, J ;
Tao, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) :489-509
[10]   Near-optimal signal recovery from random projections: Universal encoding strategies? [J].
Candes, Emmanuel J. ;
Tao, Terence .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (12) :5406-5425
1234567