Universality of first-order methods on random and deterministic matrices

📄 arXiv: 2604.11729v1 📥 PDF

作者: Nicola Gorini, Chris Jones, Dmitriy Kunisky, Lucas Pesenti

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

发布日期: 2026-04-13

💡 一句话要点

通过分析流量分布，提升一阶方法在随机和确定性矩阵上的通用性

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

关键词: 通用一阶方法 近似消息传递 流量分布 确定性矩阵 随机矩阵

📋 核心要点

  1. 现有通用一阶方法（GFOM）在处理结构化输入矩阵时，难以保持状态的高斯性，限制了其适用范围。
  2. 论文通过分析输入矩阵的极限流量分布，设计了一种新的AMP迭代算法，使其能处理更广泛的输入类型。
  3. 新算法的渐近动态适用于包含随机和确定性输入矩阵的流量分布，并对Onsager校正给出了组合解释。

📝 摘要（中文）

本文研究了一类灵活的迭代算法，即通用一阶方法(GFOM)，该方法通过矩阵-向量乘法和逐元素非线性运算来更新状态向量。大量研究致力于理解GFOM在大n下的动态特性，主要集中在“非常随机”的输入矩阵以及状态渐近高斯的GFOM的近似消息传递(AMP)特殊情况。然而，如何构建迭代算法，使其在更结构化的输入下保持这种高斯性，或者为什么现有的AMP算法对于某些确定性矩阵与随机矩阵一样有效，长期以来仍然未知。我们通过输入矩阵的极限流量分布（矩阵条目中排列不变多项式的所有极限值的集合）分析了GFOM的图解展开，从而获得了以下结果：1. 我们计算了第一个非平凡确定性矩阵的流量分布，包括（次要变体）Walsh-Hadamard和离散正弦和余弦变换矩阵。这确定了GFOM在这些输入上的极限动态，解决了Marinari、Parisi和Ritort（1994）长期存在的猜想的部分内容。2. 我们设计了一种新的AMP迭代，它统一了之前的几种AMP变体，并推广到新的输入类型，其极限动态是有条件地以一些潜在随机变量为条件的高斯分布。渐近动态适用于一大类自然的流量分布（包括随机和确定性输入矩阵），并且该算法的分析给出了Onsager校正的简单组合解释，回答了Wang、Zhong和Fan（2022）最近提出的问题。

🔬 方法详解

问题定义：现有通用一阶方法（GFOM）在处理非随机或结构化的输入矩阵时，其状态向量难以保持渐近高斯性，导致近似消息传递（AMP）算法的性能下降或失效。此外，对于某些确定性矩阵，现有AMP算法的有效性缺乏理论解释。因此，需要设计一种更通用的AMP算法，使其能够处理更广泛的输入矩阵类型，并解释其有效性。

核心思路：论文的核心思路是通过分析输入矩阵的极限流量分布来理解GFOM的动态特性。极限流量分布描述了矩阵条目中排列不变多项式的极限行为，可以捕捉矩阵的结构信息。基于流量分布，论文设计了一种新的AMP迭代算法，该算法能够适应不同类型的输入矩阵，并保持状态向量的渐近高斯性。

技术框架：论文的技术框架主要包括以下几个步骤：1. 定义通用一阶方法（GFOM）的迭代过程。2. 引入输入矩阵的极限流量分布的概念。3. 基于流量分布，推导GFOM的图解展开式。4. 设计一种新的AMP迭代算法，该算法能够利用流量分布的信息。5. 分析新算法的渐近动态，证明其状态向量的渐近高斯性。6. 将新算法应用于不同的输入矩阵，并验证其性能。

关键创新：论文的关键创新在于：1. 提出了利用输入矩阵的极限流量分布来分析GFOM动态特性的方法。2. 设计了一种新的AMP迭代算法，该算法能够处理更广泛的输入矩阵类型，并保持状态向量的渐近高斯性。3. 对Onsager校正给出了简单的组合解释，解决了现有AMP算法中长期存在的问题。

关键设计：新AMP算法的关键设计包括：1. 利用流量分布的信息来更新状态向量。2. 引入潜在随机变量来建模输入矩阵的结构信息。3. 使用适当的非线性函数来保证状态向量的渐近高斯性。具体的参数设置和损失函数取决于具体的应用场景和输入矩阵的类型。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文计算了Walsh-Hadamard和离散正弦/余弦变换矩阵等确定性矩阵的流量分布，解决了Marinari等人长期存在的猜想的部分内容。此外，新设计的AMP算法统一了之前的多种变体，并推广到新的输入类型，其渐近动态适用于包含随机和确定性输入矩阵的流量分布，并对Onsager校正给出了组合解释。

🎯 应用场景

该研究成果可应用于信号处理、图像恢复、机器学习等领域，特别是在处理具有特定结构的矩阵数据时，例如压缩感知、低秩矩阵恢复等。通过利用该方法，可以设计出更高效、更鲁棒的算法，提高相关任务的性能。此外，该研究对于理解和改进现有的AMP算法具有重要的理论意义。

📄 摘要（原文）

General first-order methods (GFOM) are a flexible class of iterative algorithms which update a state vector by matrix-vector multiplications and entrywise nonlinearities. A long line of work has sought to understand the large-n dynamics of GFOM, mostly focusing on "very random" input matrices and the approximate message passing (AMP) special case of GFOM whose state is asymptotically Gaussian. Yet, it has long remained unknown how to construct iterative algorithms that retain this Gaussianity for more structured inputs, or why existing AMP algorithms can be as effective for some deterministic matrices as they are for random matrices. We analyze diagrammatic expansions of GFOM via the limiting traffic distribution of the input matrix, the collection of all limiting values of permutation-invariant polynomials in the matrix entries, to obtain the following results: 1. We calculate the traffic distribution for the first non-trivial deterministic matrices, including (minor variants of) the Walsh-Hadamard and discrete sine and cosine transform matrices. This determines the limiting dynamics of GFOM on these inputs, resolving parts of longstanding conjectures of Marinari, Parisi, and Ritort (1994). 2. We design a new AMP iteration which unifies several previous AMP variants and generalizes to new input types, whose limiting dynamics are Gaussian conditional on some latent random variables. The asymptotic dynamics hold for a large and natural class of traffic distributions (encompassing both random and deterministic input matrices) and the algorithm's analysis gives a simple combinatorial interpretation of the Onsager correction, answering questions posed recently by Wang, Zhong, and Fan (2022).