Approximate message passing shows universal behavior for rank one quadratic sensing
Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
Information Theory
Summary
This paper studies an algorithm called Approximate Message Passing (AMP), which is used to solve certain problems involving quadratic measurements. The authors show that AMP behaves similarly even when the data has complex dependencies, as long as it matches certain statistical properties of simpler Gaussian data. This means the performance and predictions for AMP stay consistent across different data types, making it more reliable in applications like quadratic regression and learning in neural networks. Their proof confirms a previous conjecture about this universal behavior.
What this means in practice
- •For machine learning engineers: Design more reliable algorithms for training quadratic neural networks by leveraging proven universality properties of AMP.
- •For statistical data scientists: Use AMP algorithms with rank-one quadratic data in regression contexts knowing performance predictions hold as if data were Gaussian.
A theory result. No direct application yet.
Authors
Duy Thuc Nguyen, Yue M. Lu, Subhabrata Sen
Abstract
Approximate Message Passing (AMP) algorithms are attractive as they are computationally efficient and simultaneously admit a precise characterization in terms of the low-dimensional "state-evolution" recursion. In this work, we establish quantitative universality for AMP with centered rank-one sensing matrices $Z_i=(x_ix_i^\top-I_d)/\sqrt d$, where $x_i$ are independent standard Gaussian vectors. These matrices arise in quadratic regression and learning quadratic neural networks. Their normalized vectorizations have isotropic covariance in dimension $p=d(d+1)/2$, but strongly dependent coordinates. For linear observations with Gaussian noise and prescribed smooth, bounded spectral denoisers, we compare rank-one sensing with a covariance-matched isotropic Gaussian ensemble. At a fixed iteration horizon, with $n\leq Cp$ and uniform bounds on the normalized signal energy, initialization, coefficients, and first four denoiser derivatives, normalized signal overlaps, cross-time overlaps, and smooth linear spectral statistics differ by $O(d^{-1/2})$ in every fixed $L^m$. This yields universality of the normalized mean-squared error, fixed spectral moments, and empirical spectral distributions. Whenever the Gaussian observables admit a joint state-evolution limit, the same predictions hold under rank-one sensing. The proof uses columnwise Lindeberg replacement, leave-one-out analysis, smooth spectral expansions, and high-moment concentration. For prescribed smooth spectral denoisers, the result establishes the AMP universality conjectured by Maillard et al. (arXiv:2408.03733).