On Universality of Non-Separable Approximate Message Passing Algorithms

📄 arXiv: 2506.23010v1 📥 PDF

作者: Max Lovig, Tianhao Wang, Zhou Fan

分类: math.ST, cs.IT, cs.LG, math.PR

发布日期: 2025-06-28

💡 一句话要点

研究非可分近似消息传递算法的普适性，扩展其在非高斯数据下的适用范围

🎯 匹配领域: 支柱八：物理动画 (Physics-based Animation)

关键词: 近似消息传递 非可分算法 普适性 平均场理论 非高斯数据

📋 核心要点

  1. 现有平均场理论对非可分算法的刻画主要局限于高斯或旋转不变数据，限制了其应用范围。
  2. 论文提出有界组合性质(BCP)和BCP可近似性条件，为非高斯数据下的非可分AMP算法普适性提供理论基础。
  3. 证明了局部去噪器、谱去噪器等常见非线性是BCP可近似的，扩展了AMP算法的适用范围。

📝 摘要（中文）

本文针对非可分近似消息传递(AMP)算法的普适性展开研究。现有对一阶迭代算法（包括AMP、随机和近端梯度下降以及Langevin扩散）的平均场刻画，已使人们能够精确理解许多统计应用中的学习动态。对于非线性项具有坐标可分形式的算法，已知这种刻画在底层数据分布方面具有一定的普适性。然而，非可分算法动态的平均场刻画在很大程度上仍局限于独立同分布的高斯或旋转不变数据。本文针对具有多项式非线性的AMP算法，提出了有界组合性质(BCP)这一通用条件，如果其表示张量满足该条件，则AMP算法的状态演化对于具有非高斯项的矩阵普遍成立。进一步形式化了Lipschitz AMP算法的BCP可近似性条件，使其具有类似的通用保证。证明了许多常见的非可分非线性类是BCP可近似的，包括局部去噪器、通用信号的谱去噪器以及可分函数与通用线性映射的组合，这意味着采用这些非线性的AMP算法的状态演化的普适性。

🔬 方法详解

问题定义：现有近似消息传递(AMP)算法的平均场理论分析，在非可分非线性情况下，主要局限于高斯或旋转不变数据。这限制了AMP算法在更广泛数据分布下的应用。因此，需要研究非可分AMP算法在非高斯数据下的普适性，即其状态演化是否与具体的数据分布无关。

核心思路：论文的核心思路是找到一个通用的条件，使得非可分AMP算法的状态演化在非高斯数据下仍然成立。为此，论文提出了有界组合性质(Bounded Composition Property, BCP)和BCP可近似性这两个概念。如果AMP算法的非线性项满足这些条件，则其状态演化具有普适性。

技术框架：论文主要通过数学推导和证明来建立普适性理论。首先，针对具有多项式非线性的AMP算法，证明了如果其表示张量满足BCP，则状态演化具有普适性。然后，针对Lipschitz AMP算法，提出了BCP可近似性的概念，并证明了如果非线性项可以被BCP函数近似，则状态演化也具有普适性。

关键创新：论文最重要的技术创新点在于提出了BCP和BCP可近似性这两个概念，为非可分AMP算法的普适性提供了理论基础。与现有方法相比，该方法不再局限于高斯或旋转不变数据，而是可以处理更广泛的数据分布。

关键设计：论文的关键设计在于如何定义BCP和BCP可近似性，以及如何证明满足这些条件的非线性项的状态演化具有普适性。具体来说，BCP要求表示张量的范数在组合运算下保持有界。BCP可近似性要求非线性项可以被BCP函数以一定的精度近似。论文还证明了许多常见的非线性项，如局部去噪器和谱去噪器，都满足BCP可近似性。

📊 实验亮点

论文证明了许多常见的非线性项，如局部去噪器、通用信号的谱去噪器以及可分函数与通用线性映射的组合，都满足BCP可近似性。这意味着采用这些非线性的AMP算法的状态演化具有普适性，可以在非高斯数据下实现有效的信号恢复和机器学习。

🎯 应用场景

该研究成果可应用于信号处理、图像恢复、机器学习等领域。通过扩展AMP算法的适用范围，使其能够在更复杂的数据环境下工作，例如非高斯噪声下的信号恢复、非结构化数据的机器学习等。未来的研究可以进一步探索更广泛的非线性项和数据分布下的普适性条件。

📄 摘要（原文）

Mean-field characterizations of first-order iterative algorithms -- including Approximate Message Passing (AMP), stochastic and proximal gradient descent, and Langevin diffusions -- have enabled a precise understanding of learning dynamics in many statistical applications. For algorithms whose non-linearities have a coordinate-separable form, it is known that such characterizations enjoy a degree of universality with respect to the underlying data distribution. However, mean-field characterizations of non-separable algorithm dynamics have largely remained restricted to i.i.d. Gaussian or rotationally-invariant data. In this work, we initiate a study of universality for non-separable AMP algorithms. We identify a general condition for AMP with polynomial non-linearities, in terms of a Bounded Composition Property (BCP) for their representing tensors, to admit a state evolution that holds universally for matrices with non-Gaussian entries. We then formalize a condition of BCP-approximability for Lipschitz AMP algorithms to enjoy a similar universal guarantee. We demonstrate that many common classes of non-separable non-linearities are BCP-approximable, including local denoisers, spectral denoisers for generic signals, and compositions of separable functions with generic linear maps, implying the universality of state evolution for AMP algorithms employing these non-linearities.