State evolution for approximate message passing with non-separable functions
State evolution for approximate message passing with non-separable functions
复制标题
DOI：
10.1093/imaiai/iay021
复制
发表时间：
2020-03-01
影响因子：
1.6
通讯作者：
Phan-Minh Nguyen
中科院分区：
文献类型：
--
作者：
Berthier, Raphael;Montanari, Andrea;Phan-Minh Nguyen
给定一个高维数据矩阵a epsilon R-mxn，近似消息传递（AMP）算法构造向量序列u(t) epsilon R-n, v(t) epsilon R-m，以t epsilon{0,1,2…}通过迭代地应用Lambda或Lambda(T)和合适的非线性函数，这取决于具体的应用。在其他应用中，这种方法的特殊实例已经被开发出来，用于压缩感知重建、鲁棒回归、贝叶斯估计、低秩矩阵恢复、相位检索和图中的社区检测。对于某类随机矩阵A， AMP允许在高维极限m， n ->∞处的渐近精确描述，并将其命名为状态演化。早期的工作建立了状态演化的可分离非线性（在一定的规则条件下）。然而，实证工作证明了几个重要的应用需要不可分离的功能。在本文中，我们将状态演化推广到Lipschitz连续不可分非线性，对于高斯矩阵a，我们的证明使用Bolthausen的条件反射技术和几个近似参数。特别地，我们引入了一个改进的算法（称为LoAMP for Long AMP），这是一个独立的兴趣。
Given a high-dimensional data matrix A epsilon R-mxn, approximate message passing (AMP) algorithms construct sequences of vectors u(t) epsilon R-n, v(t) epsilon R-m, indexed by t epsilon {0, 1, 2 . . .} by iteratively applying Lambda or Lambda(T) and suitable nonlinear functions, which depend on the specific application. Special instances of this approach have been developed-among other applications-for compressed sensing reconstruction, robust regression, Bayesian estimation, low-rank matrix recovery, phase retrieval and community detection in graphs. For certain classes of random matrices A, AMP admits an asymptotically exact description in the high-dimensional limit m, n -> infinity, which goes under the name of state evolution. Earlier work established state evolution for separable nonlinearities (under certain regularity conditions). Nevertheless, empirical work demonstrated several important applications that require non-separable functions. In this paper we generalize state evolution to Lipschitz continuous non-separable nonlinearities, for Gaussian matrices A. Our proof makes use of Bolthausen's conditioning technique along with several approximation arguments. In particular, we introduce a modified algorithm (called LoAMP for Long AMP), which is of independent interest.