Approximate message passing works under mild entry variability conditions
Universality of approximate message passing under a fourth-moment tail condition
Information Theory
Summary
Approximate message passing (AMP) is a method used to analyze large random matrices common in data science. The paper shows that AMP's performance predictions hold even when matrix entries come from different distributions, as long as their scaled fourth moments are bounded. This broadens the types of data where AMP's predictions remain reliable without needing strong assumptions like identical entry distributions or Gaussianity. The authors also clarify limits on applying Gaussian-based identity methods to non-Gaussian matrices.
What this means in practice
- •For signal processing engineers: Ensure reliable performance predictions for AMP algorithms when processing signals from diverse or non-Gaussian noise sources with finite fourth moment conditions.
- •For machine learning system builders: Design AMP-based inference systems that remain accurate on large datasets with heterogeneous data distributions satisfying only mild moment constraints.
A theory result. No direct application yet.
Authors
Ripunjay Dwivedi, Taejoon Kim
Abstract
We prove state evolution for approximate message passing (AMP) with rectangular random matrices whose entries are independent, centered, and variance-normalized. The row and column dimensions grow with a ratio that converges to a positive finite limit. The entry laws may differ across coordinates and dimensions, and we assume uniform integrability of the fourth powers of the rescaled entries. For entries sampled independently from a fixed law, a finite fourth moment suffices, with no requirement for higher moments. The nonlinearities are continuously differentiable and globally Lipschitz, with bounded continuous first state derivatives. The signal and noise have independent and identically distributed coordinates with finite moments of all orders, and are independent of each other and of the matrix. At every fixed number of iterations, empirical averages of pseudo-Lipschitz functions of order two converge in probability to the limits specified by Gaussian state evolution. These averages include empirical second moments and products of trajectory coordinates. The proof combines an aggregate bound on third derivatives with randomized Lindeberg replacement and operator-norm truncation, without matching third moments or invoking a non-Gaussian universality theorem. We also show that independence of complementary projected components for every deterministic rank-one constraint pair characterizes Gaussian entries. This identifies the limitation of extending Gaussian conditioning identities to independent non-Gaussian matrices. Finally, a variance-profile example shows that average variance normalization alone does not ensure the homogeneous state evolution limits.