Pith. sign in

REVIEW 2 major objections 4 minor 74 references

On Universality of Non-Separable Approximate Message Passing Algorithms

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For a broad class of non-separable denoisers, Approximate Message Passing keeps its Gaussian state-evolution limit even when the sensing matrix has independent non-Gaussian entries.

desk verdict First real universality theory for non-separable AMP; BCP is a genuine new condition, and the three verified classes make the framework concrete despite the lack of a simple certificate. read the letter →

arxiv 2506.23010 v1 pith:XT7PYH47 submitted 2025-06-28 math.ST cs.ITcs.LGmath.ITmath.PRstat.TH

Max Lovig , Tianhao Wang , Zhou Fan This is my paper · ORCID
classification math.STcs.ITcs.LGmath.ITmath.PRstat.TH MSC 60B2060F05
keywords approximatemessagepassinguniversalitystateevolutionnon-separablenonlinearitiesWignermatricesmomentmethodtensornetworksBoundedCompositionProperty
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Approximate Message Passing (AMP) algorithms are usually analyzed by replacing their iterates with Gaussian state-evolution vectors whose covariances are computed recursively. That substitution was known to be universal for non-Gaussian random matrices when the algorithm's nonlinearities act coordinate by coordinate. This paper extends universality to genuinely non-separable nonlinearities, provided their polynomial approximations satisfy a Bounded Composition Property controlling how much the representing tensors amplify under contraction. If the theorems are right, AMP with local image-smoothing filters, spectral singular-value denoisers on signals with generic singular vectors, and colored-design reductions has the same Gaussian state evolution for Rademacher or other i.i.d. sensing matrices as for Gaussian ones.

What carries the argument

The load-bearing object is the Bounded Composition Property (BCP) for the tensors representing homogeneous components of polynomial nonlinearities: every connected contraction of these tensors in which each summed index appears an even number of times must scale at most $O(n)$, uniformly over the tensor set and over all contraction patterns. BCP-representability means each polynomial has such a tensor decomposition; BCP-approximability extends the notion to Lipschitz maps by requiring Gaussian-input $L^2$ approximation by BCP-representable polynomials plus a density condition. The proof unrolls the AMP iterates into tensor networks and uses the BCP to control the first and fourth moments of the difference between Gaussian and non-Gaussian entry distributions.

What would settle it

Run the asymmetric AMP recursion of Example 3.5 with i.i.d. Rademacher sensing entries, a Haar-singular-vector low-rank signal, and singular-value soft-thresholding, and compare the empirical MSE to the state-evolution prediction (3.6); if the difference does not vanish as $m,n$ grow with $m/n$ bounded away from 0 and infinity, the theorem would be false.

Watch

Extended reading notes

Core claim

The central claim is that state-evolution universality holds for non-separable AMP. For symmetric AMP driven by any Wigner matrix with independent, mean-zero, matching-moment entries, polynomial nonlinearities whose tensors satisfy the Bounded Composition Property, and Lipschitz nonlinearities that are BCP-approximable, the paper proves that for test functions $\phi(z_{1:T}) = n^{-1}\phi_1(z_{1:T})^T \phi_2(z_{1:T})$ in the same classes, $\phi(z_{1:T}) - E[\phi(Z_{1:T})]$ converges to zero almost surely, where $Z_{1:T}$ are Gaussian vectors with covariance and Onsager coefficients defined recursively from Gaussian inputs. The same conclusion is proved for the asymmetric AMP recursion, covering the standard compressed-sensing form. Along the way the paper establishes a stronger Gaussian state-evolution bound, with iterate errors of order $O(\mathrm{poly}\log n)$ in $\ell^2$, for a stability class that includes BCP-representable polynomials.

Load-bearing premise

The Bounded Composition Property is assumed, not derived: if any connected tensor contraction representing the nonlinearity grows faster than order $n$, the moment-method comparison to Gaussian entries collapses.

Editorial extensions

If this is right

  • For local sliding-window or bounded-degree denoisers, the MSE prediction of AMP for linear measurement models holds for any i.i.d. sensing matrix with zero mean and bounded moments, not only Gaussian.
  • For matrix sensing, singular-value soft-thresholding denoisers applied to signals with Haar-generic singular vectors keep the Gaussian state-evolution limit with non-Gaussian sensing, so the Gaussian prediction for reconstruction MSE is trustworthy.
  • For colored or correlated measurement designs expressible as $WK$ with generic $K$, the anisotropic reduction makes the state-evolution prediction universal across the same entry distributions.
  • The asymmetric version of the theorems covers the standard compressed-sensing AMP recursion with non-separable denoisers, removing the Gaussian-only restriction on the sensing matrix.
  • The new Gaussian stability result implies a stronger, quantitative state-evolution approximation for polynomial-growth pseudo-Lipschitz maps, independently of the universality argument.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The BCP is plausibly near-necessary: the paper proves sufficiency, and its own Example 1.1 shows that a fixed-rotation conjugation violates the relevant boundedness and breaks universality; a converse characterizing exactly which non-separable maps are universal would complete the picture.
  • The approximation architecture suggests that any Lipschitz non-separable map that can be approximated on Gaussian inputs by bounded-composition polynomials, such as convolutional or bounded-receptive-field networks, should inherit the same universality even though those architectures are not analyzed here.
  • A practical consequence the authors leave implicit is that state-evolution-based performance estimates for image and matrix recovery can be used with non-Gaussian sensing matrices, which is common in hardware; this is now justified for local and spectral denoisers.
  • The genericity of singular vectors is doing real work: spectral denoisers for signals with deterministic or structured singular vectors may fall outside the theorem, so a boundary case worth testing is a sparse or otherwise structured singular-vector signal.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a universality theory for non-separable approximate message passing (AMP) algorithms driven by random matrices with independent non-Gaussian entries. The main objects are polynomial nonlinearities represented by tensors satisfying a new Bounded Composition Property (BCP, Definition 2.3) and Lipschitz nonlinearities that are BCP-approximable (Definition 2.7). The central results are Theorem 2.6 (universality of state evolution for polynomial AMP), Theorem 2.9 (extension to BCP-approximable Lipschitz AMP), and Theorem 3.3 (asymmetric AMP analogue). Three concrete classes are verified: local functions, anisotropic functions with generic linear maps, and spectral functions with generic singular vectors. The proof strategy combines a Gaussian conditioning state evolution for GOE matrices (Section 4.1, Theorem 4.2) with a tensor-network moment method comparing Gaussian and non-Gaussian Wigner matrices (Section 4.2, Lemmas 4.4, 4.5, C.6).

Significance. If correct, this is a significant step: it gives the first general sufficient condition for universality of state evolution for non-separable AMP, and the three verified function classes cover practically relevant applications such as image denoising, matrix sensing, and correlated-design reductions. The BCP condition is clean and the proofs are unusually detailed; the tensor-network moment method with Weingarten calculus appears internally consistent, and the exponent bookkeeping in Lemmas 4.5 and C.6 checks out. The main limitation is that BCP is an assumed property rather than a derived or certified one, and the spectral and anisotropic verification results require genericity hypotheses (random orthogonal matrices with bounded densities) and non-degeneracy of the state evolution covariances; these are honest scope restrictions, not internal contradictions. The manuscript would be a strong contribution once the asymmetric-model statements are corrected.

major comments (2)
  1. [Definition 3.1] The initialization of the asymmetric state evolution is inconsistent with the scaling of W. Assumption 3.2 fixes E[W[i,j]^2] = 1/m, so for z_1 = W u_1 the covariance of z_1 is m^{-1} times the norm-squared of u_1 times the identity, not n^{-1} times that quantity as written in Definition 3.1. This makes the Gaussian vectors of Theorem 3.3 mismatched with the iterates of (3.1) unless m equals n. Example 3.4 uses omega_1^2 = m^{-1} times the norm-squared of theta_*, confirming the intended normalization. Please change Omega_1 to m^{-1} times the norm-squared of u_1 and check all downstream uses of Omega_t in the asymmetric section.
  2. [Theorem 3.3] The test function psi(y_{1:T}) is defined with scaling 1/m even though psi_1 and psi_2 map to R^n and y_t has n coordinates. The natural state-evolution normalization for an n-dimensional iterate is 1/n, and the paper's own examples use this normalization: Example 3.4 defines MSE = n^{-1} times the norm-squared of psi_T(y_T) and the prediction (3.6) is n^{-1} times the expectation of the norm-squared. As stated, the 1/m scaling introduces an aspect-ratio factor n/m and does not cover the examples when m/n does not tend to 1. Please replace 1/m by 1/n in the definition of psi and in the second limit of Theorem 3.3.
minor comments (4)
  1. [Example 3.6] The statement that the singular vectors O and U of a deterministic matrix K are 'generic in the sense of condition (2) in Proposition 2.17' is not well-defined: condition (2) requires O and U to be random with densities uniformly bounded with respect to Haar measure, but for a fixed K its singular vectors are deterministic. Please reformulate the example, for instance by taking K random and independent of W, or by invoking condition (1).
  2. [Definition 2.7] Condition (2) of BCP-approximability is intricate and somewhat self-referential (it quantifies over sequences z satisfying a moment condition that is stated using the same Q set). A short paragraph after Definition 2.7 explaining how condition (2) is used and why the countable closure arguments in the examples suffice would improve readability.
  3. [Lemma E.8] In the statement of Lemma E.8, the quantiles s(j) depend on M and the measure mu, and the assertion 'for all large enough M' should be read jointly with the dependence of s(j) on M; clarifying this dependency would avoid potential confusion.
  4. [Abstract and Section 1.1] The abstract's closing sentence could be tempered slightly: the proven universality for spectral and anisotropic classes holds under genericity assumptions on the orthogonal matrices, and not for arbitrary non-separable nonlinearities; the main text is careful about this, but the abstract should match that precision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theorems are genuine implications from BCP to universality, and the state-evolution parameters are defined independently of the non-Gaussian data.

full rationale

The derivation chain is self-contained. Definition 2.1 fixes Sigma_t and b_ts as explicit Gaussian expectations involving the algorithm's nonlinearities; Theorems 2.6, 2.9, and 3.3 assert that empirical functionals of the true iterates converge to those expectations, which is not assumed but proved. The BCP (Definition 2.3) is a sufficient, non-vacuous tensor contraction bound; Example 1.1 demonstrates genuine failure without it, and the verification results (Propositions 2.14, 2.17, 2.19) establish the condition for concrete classes rather than importing it. The polynomial universality proof (Theorem 2.6) is carried out in the appendices via a Gaussian state-evolution result (Theorem 4.2 and Lemma B.2) plus an explicit moment-method comparison (Lemmas 4.5 and C.6 with the fourth-moment bound (C.8)); no fitted quantity is relabeled as a prediction. The Lipschitz extension (Theorem 2.9) is a standard polynomial-approximation reduction: condition (2) of Definition 2.7 is an implication, and its antecedent (2.8) is established in the proof by applying the already-proven Corollary C.7, not assumed as a conclusion. Citations to the authors' prior work [69] are for proof technique and Weingarten formulas; the needed lemmas are re-derived in the appendix, and no load-bearing premise is justified solely by a self-citation. The only limitations are scope conditions (BCP and its verification require genericity or l_infty bounds), which narrow applicability but do not make the derivation circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theory introduces no fitted parameters; every state evolution quantity is an explicit Gaussian expectation. The core new assumption is the BCP, listed as ad hoc to the paper, and the examples add clearly stated genericity assumptions. The experimental hyperparameters (h_t = 1, λ_t = 0.05) are hand-chosen for illustration only and do not enter any theorem. No new particles, mediators, dimensions, or conserved quantities are introduced.

assumptions (5)
  • domain assumption Assumptions 2.2 and 3.2: Wigner and asymmetric matrix entries are independent, mean zero, variance 1/n (or 1/m), with uniform moment bounds for k ≥ 3.
    This defines the universality class (independent entries with matching moments). Standard in the AMP universality literature, e.g. [8, 69].
  • ad hoc to paper Bounded Composition Property (Definition 2.3): the tensors representing the polynomial nonlinearities have all connected, even-index-parity contractions bounded uniformly as O(n).
    The paper's central new sufficient condition. If a contraction grows faster, the moment-method bounds break, and Example 1.1 shows some condition of this type is necessary. No converse is proven, and the paper admits the condition is abstract and not simple to check.
  • domain assumption Non-degeneracy: λ_min(Σ_t) > c for the relevant state evolution covariances, and weak differentiability of the functions f_t, so that the Onsager coefficients in (2.2) are well-defined.
    Assumed in Section 2 (footnote) and in Theorems 2.6, 2.9, and 3.3; required for the Gaussian conditioning induction (Theorem 4.2) and for the polynomial approximation argument (Appendix D).
  • domain assumption Genericity assumptions in the examples: random orthogonal matrices O and U with density bounded with respect to Haar measure, for anisotropic (Proposition 2.17) and spectral (Proposition 2.19) function classes, with ||D||_op < C√N.
    Without genericity, the anisotropic and spectral classes can fail BCP-approximability, mirroring the rotation mechanism of Example 1.1. Corollary E.7 transfers the Gaussian-shift result to such generic singular vectors via a density argument.
  • standard math Standard probabilistic and combinatorial background: Wick's rule (Lemma F.4), Gaussian hypercontractivity (Lemma F.5), Weingarten calculus, polynomial approximation with Gaussian weight (Lemma F.6), Schudy-Sviridenko-type bounds.
    Used throughout Appendices A, C, E; these are background results cited appropriately (e.g. [21, 62, 29]).

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Universality of Non-Separable Approximate Message Passing Algorithms." pith.science (2026). https://pith.science/paper/XT7PYH47

@misc{pith2026250623010,
  author       = {Pith},
  title        = {Pith review of: On Universality of Non-Separable Approximate Message Passing Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XT7PYH47}},
  note         = {Machine review of arXiv:2506.23010}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2506.23010 by the authors.

Figure 1
Figure 1. (a) AMP iterates θt ∈ RM×N of (1.1) applied with a local kernel￾smoothing denoiser and with a matrix W having either i.i.d. N (0, 1/m) or Rademacher ±1/ √ m entries. (b) Mean-squared-errors 1 n ∥θt − θ∗∥ 2 2 for the two matrices W, and the state evolution prediction. Here M = N = 150, n = 22500, and m = 0.95 n. Let u1 ∈ R n be an initialization, and f1, f2, f3, . . . a sequence of non-linear functions where ft : R n… view at source ↗
Figure 2
Figure 2. (a) Singular value spectra of the AMP iterates θt ∈ RM×N of (1.1) applied with a singular-value thresholding denoiser and with a matrix W having either i.i.d. N (0, 1/m) or Rademacher ±1/ √ m entries. (b) Mean-squared-errors 1 n ∥θt − θ∗∥ 2 2 for the two matrices W, and the state evolution prediction. Here M = 100, N = 150, and m = n = 15000. distribution N (0, Σt). Define Σt+1 ∈ R (t+1)×(t+1) entrywise by Σt+1[r+1,… view at source ↗
Figure 3
Figure 3. An example conversion from (G,L) → (G, ˇ Lˇ) → (G, ˜ L˜). (Top left) The initial graph G with labels L in T1, . . . , T5,W, and an edge partition π ∈ P(E) consisting of three blocks [1], [2], [3]. This induces two blocks [v] ∈ πW (π), one which is paired and has incident blocks [1], [2] ∈ π, and a second with k[v] = 3 and incident blocks [1], [3] ∈ π. (Top right) The graph (G, ˇ Lˇ) representing (C.4) in the case τ … view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: An example of a tensor T ∈ T for the class of polynomial anisotropic functions. the class (E.14), together with the convergence Σ → Σ¯ , imply α · lim nj→∞ 1 |Ia,˚g| X i∈Ia,˚g ˚q(z[Ai ]) = lim nj→∞ 1 nj q1(z) ⊤q2(z) = lim nj→∞ 1 nj E[q1(Z) ⊤q2(Z)] = α · EZ¯∼N (0,Σ¯ ⊗Id…
Figure 5
Figure 5. Figure 5: An example of the graph Galt representing the value of the tensor contraction (E.41). so we must show for each fixed m, ℓ, k1, . . . , km and π that |val| ≤ Cn for a constant C > 0 and all large n. Identifying each index i ∈ [n] with its equivalent index pair (j, j′ ) …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

74 extracted references · 64 canonical work pages

  1. [1]

    Unsourced random access with coded compressed sensing: Integrating amp and belief propagation.IEEE Transactions on Information Theory, 68(4):2384–2409, 2021

    Vamsi K Amalladinne, Asit Kumar Pradhan, Cynthia Rush, Jean-Francois Chamberland, and Krishna R Narayanan. Unsourced random access with coded compressed sensing: Integrating amp and belief propagation.IEEE Transactions on Information Theory, 68(4):2384–2409, 2021

    work page 2021

  2. [2]

    Operator-lipschitz estimates for the singular value functional calculus.Proceedings of the American Mathematical Society, 144(5):1867–1875, 2016

    Fredrik Andersson, Marcus Carlsson, and Karl-Mikael Perfekt. Operator-lipschitz estimates for the singular value functional calculus.Proceedings of the American Mathematical Society, 144(5):1867–1875, 2016

    work page 2016

  3. [3]

    Large deviations for langevin spin glass dynamics

    Gerard Ben Arous and Alice Guionnet. Large deviations for langevin spin glass dynamics. Probability Theory and Related Fields, 102:455–509, 1995

    work page 1995

  4. [4]

    Symmetric langevin spin glass dynamics.The Annals of Probability, 25(3):1367–1422, 1997

    Gerard Ben Arous and Alice Guionnet. Symmetric langevin spin glass dynamics.The Annals of Probability, 25(3):1367–1422, 1997

    work page 1997

  5. [5]

    Inferring change points in high- dimensional linear regression via approximate message passing

    Gabriel Arpino, Xiaoqi Liu, and Ramji Venkataramanan. Inferring change points in high- dimensional linear regression via approximate message passing. InForty-first International Conference on Machine Learning, 2024

    work page 2024

  6. [6]

    The spiked matrix model with generative priors.Advances in Neural Information Processing Systems, 32, 2019

    Benjamin Aubin, Bruno Loureiro, Antoine Maillard, Florent Krzakala, and Lenka Zdeborová. The spiked matrix model with generative priors.Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  7. [7]

    A leave-one-out approach to approximate message passing

    Zhigang Bao, Qiyang Han, and Xiaocong Xu. A leave-one-out approach to approximate message passing. arXiv preprint arXiv:2312.05911, 2023

    arXiv 2023

  8. [8]

    Universality in polytope phase transitions and message passing algorithms.The Annals of Applied Probability, 25(2), April 2015

    Mohsen Bayati, Marc Lelarge, and Andrea Montanari. Universality in polytope phase transitions and message passing algorithms.The Annals of Applied Probability, 25(2), April 2015

    work page 2015

Show all 74 references
  1. [9]

    The dynamics of message passing on dense graphs, with applications to compressed sensing.IEEE Transactions on Information Theory, 57(2):764–785, February 2011

    Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing.IEEE Transactions on Information Theory, 57(2):764–785, February 2011

    2011

  2. [10]

    Online stochastic gradient descent on non-convex losses from high-dimensional inference.Journal of Machine Learning Research, 22(106):1–51, 2021

    Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference.Journal of Machine Learning Research, 22(106):1–51, 2021

    2021

  3. [11]

    High-dimensional limit theorems for sgd: Effective dynamics and critical scaling.Advances in neural information processing systems, 35:25349–25362, 2022

    Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for sgd: Effective dynamics and critical scaling.Advances in neural information processing systems, 35:25349–25362, 2022

    2022

  4. [12]

    State evolution for approximate message passing with non-separable functions.Information and Inference: A Journal of the IMA, 9(1):33–79, 01 2019

    Raphaël Berthier, Andrea Montanari, and Phan-Minh Nguyen. State evolution for approximate message passing with non-separable functions.Information and Inference: A Journal of the IMA, 9(1):33–79, 01 2019

    2019

  5. [13]

    Billingsley.Probability and Measure

    P. Billingsley.Probability and Measure. Wiley Series in Probability and Statistics. Wiley, 2012

    2012

  6. [14]

    An iterative construction of solutions of the tap equations for the sherrington– kirkpatrick model

    Erwin Bolthausen. An iterative construction of solutions of the tap equations for the sherrington– kirkpatrick model. Communications in Mathematical Physics, 325(1):333–366, 2014

    2014

  7. [15]

    Algorithmic analysis and statis- tical estimation of slope via approximate message passing.IEEE Transactions on Information Theory, 67(1):506–537, 2020

    Zhiqi Bu, Jason M Klusowski, Cynthia Rush, and Weijie J Su. Algorithmic analysis and statis- tical estimation of slope via approximate message passing.IEEE Transactions on Information Theory, 67(1):506–537, 2020

    2020

  8. [16]

    Characterizing the slope trade-off: A variational perspective and the donoho–tanner limit.The Annals of Statistics, 51(1):33–61, 2023

    Zhiqi Bu, Jason M Klusowski, Cynthia Rush, and Weijie J Su. Characterizing the slope trade-off: A variational perspective and the donoho–tanner limit.The Annals of Statistics, 51(1):33–61, 2023. ON UNIVERSALITY OF NON-SEPARABLE APPROXIMATE MESSAGE PASSING ALGORITHMS 23

    2023

  9. [17]

    The high-dimensional asymptotics of first order methods with random data.arXiv preprint arXiv:2112.07572, 2021

    Michael Celentano, Chen Cheng, and Andrea Montanari. The high-dimensional asymptotics of first order methods with random data.arXiv preprint arXiv:2112.07572, 2021

    2021 arXiv

  10. [18]

    The estimation error of general first order methods

    Michael Celentano, Andrea Montanari, and Yuchen Wu. The estimation error of general first order methods. InProceedings of Thirty Third Conference on Learning Theory, pages 1078–1141. PMLR, 2020

    2020

  11. [19]

    Universality of approximate message passing algorithms

    Wei Kuo Chen and Wai-Kit Lam. Universality of approximate message passing algorithms. Electronic Journal of Probability, 26:36, 2021

    2021

  12. [20]

    Weingarten calculus via orthogonality relations: new applications

    Benoit Collins and Sho Matsumoto. Weingarten calculus via orthogonality relations: new applications. Latin American Journal of Probability and Mathematical Statistics, 14(1):631, 2017

    2017

  13. [21]

    Integration with respect to the haar measure on unitary, orthogonal and symplectic group.Communications in Mathematical Physics, 264(3):773–795, 2006

    Benoit Collins and Piotr Sniady. Integration with respect to the haar measure on unitary, orthogonal and symplectic group.Communications in Mathematical Physics, 264(3):773–795, 2006

    2006

  14. [22]

    Hitting the high-dimensional notes: An ode for sgd learning dynamics on glms and multi-index models

    Elizabeth Collins-Woodfin, Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the high-dimensional notes: An ode for sgd learning dynamics on glms and multi-index models. Information and Inference: A Journal of the IMA, 13(4):iaae028, 2024

    2024

  15. [23]

    Diffusions interacting through a random matrix: universality via stochastic taylor expansion.Probability Theory and Related Fields, 180:1057–1097, 2021

    Amir Dembo and Reza Gheissari. Diffusions interacting through a random matrix: universality via stochastic taylor expansion.Probability Theory and Related Fields, 180:1057–1097, 2021

    2021

  16. [24]

    Universality for langevin-like spin glass dynamics

    Amir Dembo, Eyal Lubetzky, and Ofer Zeitouni. Universality for langevin-like spin glass dynamics. The Annals of applied probability, 31(6):2864–2880, 2021

    2021

  17. [25]

    David L Donoho, Matan Gavish, and Andrea Montanari. The phase transition of matrix recovery from gaussian measurements matches the minimax mse of matrix denoising.Proceedings of the National Academy of Sciences, 110(21):8405–8410, 2013

    2013

  18. [26]

    Donoho, Arian Maleki, and Andrea Montanari

    David L. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914–18919, November 2009

    2009

  19. [27]

    Lu, and Subhabrata Sen

    Rishabh Dudeja, Yue M. Lu, and Subhabrata Sen. Universality of approximate message passing with semirandom matrices.The Annals of Probability, 51(5):1616 – 1683, 2023

    2023

  20. [28]

    Rishabh Dudeja, Subhabrata Sen, and Yue M. Lu. Spectral universality in regularized linear regression with nearly deterministic sensing matrices. IEEE Transactions on Information Theory, 70(11):7923–7951, 2024

    2024

  21. [29]

    On weighted uniform approximation by polynomials of functions of several variables.Matematicheskii Sbornik, 85(2):227–256, 1957

    Mkhitar Mkrtichevich Dzhrbashyan and AB Tavadyan. On weighted uniform approximation by polynomials of functions of several variables.Matematicheskii Sbornik, 85(2):227–256, 1957

    1957

  22. [30]

    Dynamical mean-field analysis of adaptive langevin diffusions: Propagation-of-chaos and convergence of the linear response

    Zhou Fan, Justin Ko, Bruno Loureiro, Yue M Lu, and Yandi Shen. Dynamical mean-field analysis of adaptive langevin diffusions: Propagation-of-chaos and convergence of the linear response. arXiv preprint arXiv:2504.15556, 2025

    2025

  23. [31]

    Dynamical mean-field analysis of adaptive langevin diffusions: Replica-symmetric fixed point and empirical bayes

    Zhou Fan, Justin Ko, Bruno Loureiro, Yue M Lu, and Yandi Shen. Dynamical mean-field analysis of adaptive langevin diffusions: Replica-symmetric fixed point and empirical bayes. arXiv preprint arXiv:2504.15558, 2025

    2025

  24. [32]

    Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J

    Oliver Y. Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth. A unifying tutorial on approximate message passing.Foundations and Trends® in Machine Learning, 15(4):335–536, 2022

    2022

  25. [33]

    On complete functions in jucys-murphy elements.Annals of Combinatorics, 16:677–707, 2012

    Valentin Féray. On complete functions in jucys-murphy elements.Annals of Combinatorics, 16:677–707, 2012

    2012

  26. [34]

    Rigorous dynamical mean-field theory for stochastic gradient descent methods.SIAM Journal on Mathematics of Data Science, 6(2):400–427, 2024

    Cedric Gerbelot, Emanuele Troiani, Francesca Mignacco, Florent Krzakala, and Lenka Zde- borova. Rigorous dynamical mean-field theory for stochastic gradient descent methods.SIAM Journal on Mathematics of Data Science, 6(2):400–427, 2024

    2024

  27. [35]

    Graph-based approximate message passing iterations†

    Cédric Gerbelot and Raphaël Berthier. Graph-based approximate message passing iterations†. Information and Inference: A Journal of the IMA, 12(4):2562–2628, 09 2023. 24 ON UNIVERSALITY OF NON-SEPARABLE APPROXIMATE MESSAGE PASSING ALGORITHMS

    2023

  28. [36]

    Walid Hachem. Approximate message passing for sparse matrices with application to the equilibria of large ecological lotka–volterra systems.Stochastic Processes and their Applications, 170:104276, 2024

    2024

  29. [37]

    Entrywise dynamics and universality of general first order methods.arXiv preprint arXiv:2406.19061, 2024

    Qiyang Han. Entrywise dynamics and universality of general first order methods.arXiv preprint arXiv:2406.19061, 2024

    2024 arXiv

  30. [38]

    Gradient descent inference in empirical risk minimization.arXiv preprint arXiv:2412.09498, 2024

    Qiyang Han and Xiaocong Xu. Gradient descent inference in empirical risk minimization.arXiv preprint arXiv:2412.09498, 2024

    2024

  31. [39]

    On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables.Biometrika, 12(1/2):134–139, 1918

    Leon Isserlis. On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables.Biometrika, 12(1/2):134–139, 1918

    1918

  32. [40]

    State evolution for general approximate message passing algorithms, with applications to spatial coupling.Information and Inference: A Journal of the IMA, 2(2):115–144, 12 2013

    Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling.Information and Inference: A Journal of the IMA, 2(2):115–144, 12 2013

    2013

  33. [41]

    Fourier analysis of iterative algorithms

    Chris Jones and Lucas Pesenti. Fourier analysis of iterative algorithms. arXiv preprint arXiv:2404.07881, 2024

    2024 arXiv

  34. [42]

    Approximate message passing from random initialization with applications to z2 synchronization.Proceedings of the National Academy of Sciences, 120(31):e2302930120, 2023

    Gen Li, Wei Fan, and Yuting Wei. Approximate message passing from random initialization with applications to z2 synchronization.Proceedings of the National Academy of Sciences, 120(31):e2302930120, 2023

    2023

  35. [43]

    Fluctuations, bias, variance & ensemble of learners: Exact asymptotics for convex losses in high-dimension

    Bruno Loureiro, Cedric Gerbelot, Maria Refinetti, Gabriele Sicuro, and Florent Krzakala. Fluctuations, bias, variance & ensemble of learners: Exact asymptotics for convex losses in high-dimension. In International conference on machine learning, pages 14283–14314. PMLR, 2022

    2022

  36. [44]

    Learning gaussian mixtures with generalized linear models: Precise asymp- totics in high-dimensions.Advances in Neural Information Processing Systems, 34:10144–10157, 2021

    Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalized linear models: Precise asymp- totics in high-dimensions.Advances in Neural Information Processing Systems, 34:10144–10157, 2021

    2021

  37. [46]

    Analysis of approximate message passing with non-separable denoisers and markov random field priors.IEEE Transactions on Information Theory, 65(11):7367–7389, 2019

    Yanting Ma, Cynthia Rush, and Dror Baron. Analysis of approximate message passing with non-separable denoisers and markov random field priors.IEEE Transactions on Information Theory, 65(11):7367–7389, 2019

    2019

  38. [47]

    Approximate message passing algorithm with universal denoising and gaussian mixture learning.IEEE Transactions on Signal Processing, 64(21):5611–5622, 2016

    Yanting Ma, Junan Zhu, and Dror Baron. Approximate message passing algorithm with universal denoising and gaussian mixture learning.IEEE Transactions on Signal Processing, 64(21):5611–5622, 2016

    2016

  39. [48]

    Complex dynamics in simple neural networks: Understanding gradient flow in phase retrieval.Advances in Neural Information Processing Systems, 33:3265– 3274, 2020

    Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Complex dynamics in simple neural networks: Understanding gradient flow in phase retrieval.Advances in Neural Information Processing Systems, 33:3265– 3274, 2020

    2020

  40. [49]

    Marvels and pitfalls of the langevin algorithm in noisy high- dimensional inference

    Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Marvels and pitfalls of the langevin algorithm in noisy high- dimensional inference. Physical Review X, 10(1):011057, 2020

    2020

  41. [50]

    Passed& spurious: Descent algorithms and local minima in spiked matrix-tensor models

    StefanoSaraoMannelli, FlorentKrzakala, PierfrancescoUrbani, andLenkaZdeborova. Passed& spurious: Descent algorithms and local minima in spiked matrix-tensor models. Ininternational conference on machine learning, pages 4333–4342. PMLR, 2019

    2019

  42. [51]

    Approximate message-passing for convex optimization with non-separable penalties.arXiv preprint arXiv:1809.06304, 2018

    Andre Manoel, Florent Krzakala, Gaël Varoquaux, Bertrand Thirion, and Lenka Zdeborová. Approximate message-passing for convex optimization with non-separable penalties.arXiv preprint arXiv:1809.06304, 2018

    2018 arXiv

  43. [52]

    Learned d-amp: Principled neural network based compressive image recovery.Advances in neural information processing systems, 30, 2017

    Chris Metzler, Ali Mousavi, and Richard Baraniuk. Learned d-amp: Principled neural network based compressive image recovery.Advances in neural information processing systems, 30, 2017. ON UNIVERSALITY OF NON-SEPARABLE APPROXIMATE MESSAGE PASSING ALGORITHMS 25

    2017

  44. [53]

    Bm3d-amp: A new image recovery algorithm based on bm3d denoising

    Christopher A Metzler, Arian Maleki, and Richard G Baraniuk. Bm3d-amp: A new image recovery algorithm based on bm3d denoising. In2015 IEEE international conference on image processing (ICIP), pages 3116–3120. IEEE, 2015

    2015

  45. [54]

    From denoising to compressed sensing

    Christopher A Metzler, Arian Maleki, and Richard G Baraniuk. From denoising to compressed sensing. IEEE Transactions on Information Theory, 62(9):5117–5144, 2016

    2016

  46. [55]

    Dynamical decoupling of generalization and overfitting in large two-layer networks.arXiv preprint arXiv:2502.21269, 2025

    Andrea Montanari and Pierfrancesco Urbani. Dynamical decoupling of generalization and overfitting in large two-layer networks.arXiv preprint arXiv:2502.21269, 2025

    2025

  47. [56]

    Homogenization of sgd in high-dimensions: Exact dynamics and generalization properties.Mathematical Programming, pages 1–90, 2024

    Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. Homogenization of sgd in high-dimensions: Exact dynamics and generalization properties.Mathematical Programming, pages 1–90, 2024

    2024

  48. [57]

    Generalized approximate message passing for estimation with random linear mixing

    Sundeep Rangan. Generalized approximate message passing for estimation with random linear mixing. In 2011 IEEE International Symposium on Information Theory Proceedings, pages 2168–2172, 2011

    2011

  49. [58]

    Fletcher

    Sundeep Rangan, Philip Schniter, and Alyson K. Fletcher. Vector approximate message passing. In 2017 IEEE International Symposium on Information Theory (ISIT), page 1588–1592. IEEE Press, 2017

    2017

  50. [59]

    Near-optimal matrix recovery from random linear measure- ments

    Elad Romanov and Matan Gavish. Near-optimal matrix recovery from random linear measure- ments. Proceedings of the National Academy of Sciences, 115(28):7200–7205, 2018

    2018

  51. [60]

    Finite sample analysis of approximate message passing algorithms

    Cynthia Rush and Ramji Venkataramanan. Finite sample analysis of approximate message passing algorithms. IEEE Transactions on Information Theory, 64(11):7264–7286, 2018

    2018

  52. [61]

    Turbo reconstruction of structured sparse signals

    Philip Schniter. Turbo reconstruction of structured sparse signals. In 2010 44th Annual Conference on Information Sciences and Systems (CISS), pages 1–6. IEEE, 2010

    2010

  53. [62]

    Concentration and moment inequalities for polynomials of independent random variables

    Warren Schudy and Maxim Sviridenko. Concentration and moment inequalities for polynomials of independent random variables. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 437–446. SIAM, 2012

    2012

  54. [63]

    On the empirical distribution of eigenvalues of a class of large dimensional random matrices.Journal of Multivariate analysis, 54(2):175–192, 1995

    Jack W Silverstein and Zhi Dong Bai. On the empirical distribution of eigenvalues of a class of large dimensional random matrices.Journal of Multivariate analysis, 54(2):175–192, 1995

    1995

  55. [64]

    Compressive imaging using approximate message passing and a markov-tree prior.IEEE transactions on signal processing, 60(7):3439–3448, 2012

    Subhojit Som and Philip Schniter. Compressive imaging using approximate message passing and a markov-tree prior.IEEE transactions on signal processing, 60(7):3439–3448, 2012

    2012

  56. [65]

    Compressive imaging via approximate message passing with image denoising.IEEE Transactions on Signal Processing, 63(8):2085–2092, 2015

    Jin Tan, Yanting Ma, and Dror Baron. Compressive imaging via approximate message passing with image denoising.IEEE Transactions on Signal Processing, 63(8):2085–2092, 2015

    2015

  57. [66]

    Approximate message passing with restricted boltzmann machine priors.Journal of Statistical Mechanics: Theory and Experiment, 2016(7):073401, 2016

    Eric W Tramel, Angélique Drémeau, and Florent Krzakala. Approximate message passing with restricted boltzmann machine priors.Journal of Statistical Mechanics: Theory and Experiment, 2016(7):073401, 2016

    2016

  58. [67]

    Springer, 2008

    Cédric Villani.Optimal transport: old and new, volume 338. Springer, 2008

    2008

  59. [68]

    Glamp: An approximate message passing framework for transfer learning with applications to lasso-based estimators.arXiv preprint arXiv:2505.22594, 2025

    Longlin Wang, Yanke Song, Kuanhao Jiang, and Pragya Sur. Glamp: An approximate message passing framework for transfer learning with applications to lasso-based estimators.arXiv preprint arXiv:2505.22594, 2025

    2025 arXiv

  60. [69]

    Universality of approximate message passing algorithms and tensor networks.The Annals of Applied Probability, 34(4):3943–3994, 2024

    Tianhao Wang, Xinyi Zhong, and Zhou Fan. Universality of approximate message passing algorithms and tensor networks.The Annals of Applied Probability, 34(4):3943–3994, 2024

    2024

  61. [70]

    Fundamental lim- its of matrix sensing: Exact asymptotics, universality, and applications

    Yizhou Xu, Antoine Maillard, Lenka Zdeborová, and Florent Krzakala. Fundamental lim- its of matrix sensing: Exact asymptotics, universality, and applications. arXiv preprint arXiv:2503.14121, 2025

    2025

  62. [71]

    Matrix denoising with doubly heteroscedastic noise: Fun- damental limits and optimal spectral methods

    Yihan Zhang and Marco Mondelli. Matrix denoising with doubly heteroscedastic noise: Fun- damental limits and optimal spectral methods. InThe Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. 26 ON UNIVERSALITY OF NON-SEPARABLE APPROXIMATE MESSAGE ...

    2024

  63. [72]

    LetPu1 = u1u⊤ 1/∥u1∥2 2 be the projection onto the span ofu1, and P⊥ u1 = Id− Pu1

    (B.1) Note thatn−1∥u1∥2 2 = Σ1, which is strictly positive by assumption. LetPu1 = u1u⊤ 1/∥u1∥2 2 be the projection onto the span ofu1, and P⊥ u1 = Id− Pu1. Let ξ1∼N (0,n−1∥u1∥2 2· Pu1)∈ Rn be a Gaussian vector independent ofW, and set Z1 = P⊥ u1z1 + ξ1, E1 = Pu1z1− ξ1. Then z...

  64. [73]

    An example conversion from(G,L)→ ( ˇG, ˇL)→ ( ˜G, ˜L)

    [2] [3] [1][1] [3] [2] [1] [3] [1] → Id M3 IdId Id T1 T2 T3 T4 T5 ⟨1⟩⟨2⟩ ⟨3⟩ ˇVId ˇVW ˇVT Id Id Id Id T1 T2 T3 T4 T5 T1 T2 T3 T4 T5 ⟨2⟩1 ⟨2⟩2 ⟨1⟩ ⟨3⟩ V1 T V2 T ˜VId → (G,L) ( ˇG, ˇL) ( ˜G, ˜L) Figure 3. An example conversion from(G,L)→ ( ˇG, ˇL)→ ( ˜G, ˜L). (Top left) The init...

  65. [74]

    Since z1 = W u1 and ˜z1 = W˜u1, (3) holds by (1) and the operator norm bound∥W∥op< 3 a.s

    (2) is vacuous. Since z1 = W u1 and ˜z1 = W˜u1, (3) holds by (1) and the operator norm bound∥W∥op< 3 a.s. for all largen. (4) holds by (1) and the definitionsΣ1 =n−1∥u1∥2 2 and ~Σ1 =n−1∥˜u1∥2 2. Now suppose inductively that statements (1–4) all hold for1,...,t , wheret≤T− 1. W...

  66. [75]

    placeholders

    Iterating this contraction procedure until G′ has only two verticesw,x, we obtain |valG(L)|≤ n∑ i=1 |Tw[i]|·| Tx[i]| where Tw, Tx∈ Rn have all entries bounded by a constant depending only onC0 and G. This shows|valG(L)|≤ Cn. By Definition C.2,T satisfies the BCP ifsupL|valG(L)...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.