This paper presents a unified framework to understand the dynamics of
message-passing algorithms in compressed sensing. State evolution is rigorously
analyzed for a general error model that contains the error model of approximate
message-passing (AMP), as well as that of orthogonal AMP. As a by-product, AMP
is proved to converge asymptotically if the sensing matrix is orthogonally
invariant and if the moment sequence of its asymptotic singular-value
distribution coincide with that of the Marchenko-Pastur distribution up to the
order that is at most twice as large as the maximum number of iterations.

通过研究一般误差模型下的状态演化，在压缩感知中理解消息传递算法的动态； 并通过副产品证明了，如果感知矩阵是正交不变的，并且其渐近奇异值分布的矩序列与 Marchenko-Pastur 分布的矩序列重合，最大迭代次数的两倍不超过该序列，那么 AMP 可以渐进收敛。

消息传递算法状态演化的统一框架

A Unified Framework of State Evolution for Message-Passing Algorithms

Factorizing low-rank matrices has many applications in machine learning and
statistics. For probabilistic models in the Bayes optimal setting, a general
expression for the mutual information has been proposed using heuristic
statistical physics computations, and proven in few specific cases. Here, we
show how to rigorously prove the conjectured formula for the symmetric rank-one
case. This allows to express the minimal mean-square-error and to characterize
the detectability phase transitions in a large set of estimation problems
ranging from community detection to sparse PCA. We also show that for a large
set of parameters, an iterative algorithm called approximate message-passing is
Bayes optimal. There exists, however, a gap between what currently known
polynomial algorithms can do and what is expected information theoretically.
Additionally, the proof technique has an interest of its own and exploits three
essential ingredients: the interpolation method introduced in statistical
physics by Guerra, the analysis of the approximate message-passing algorithm
and the theory of spatial coupling and threshold saturation in coding. Our
approach is generic and applicable to other open problems in statistical
estimation where heuristic statistical physics predictions are available.

该论文研究如何采用严谨的方法证明低秩矩阵的对称秩一情况的互信息，进而表达最小均方误差和表征检测相位转变；同时介绍了一种被称为近似消息传递的迭代算法在贝叶斯最优条件下的优越性，并提出了通用的解决其他问题的方法。

对称秩一矩阵估计的互信息：复制公式的证明

Mutual information for symmetric rank-one matrix estimation: A proof of  the replica formula

In this work we propose a novel iterative estimation algorithm for linear
observation systems called S-AMP whose fixed points are the stationary points
of the exact Gibbs free energy under a set of (first- and second-) moment
consistency constraints in the large system limit. S-AMP extends the
approximate message-passing (AMP) algorithm to general matrix ensembles. The
generalization is based on the S-transform (in free probability) of the
spectrum of the measurement matrix. Furthermore, we show that the optimality of
S-AMP follows directly from its design rather than from solving a separate
optimization problem as done for AMP.

本文介绍了一种新型的迭代估计算法 S-AMP，其固定点是在一组（一阶和二阶）矩匹配约束下准确吉布斯自由能的静止点，在大系统极限下。该算法基于测量矩阵的频谱的 S 变换，并将近似信息传递（AMP）算法推广到一般矩阵集合上。此外，我们还表明，S-AMP 的最优性是直接由其设计而不是通过解决单独的优化问题（如 AMP 算法）而实现的。