Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
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 Zi=(xixi⊤−Id)/√d, where xi 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≤ 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 Lm. 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).
Related
- Universality of approximate message passing under a fourth-moment tail condition
- Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem
- On the State Evolution of Approximate Message Passing with Discontinuous Denoisers
- Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
- DAIF: A Data-Driven Intermediate Fusion Framework for Multimodal Supervised Learning via Approximate Message Passing
BibTeX
@misc{nguyen2026quantitative,
title = {{Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing}},
author = {Duy Thuc Nguyen and Yue M. Lu and Subhabrata Sen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05327},
eprint = {2610.05327},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05327},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
AU - Duy Thuc Nguyen
AU - Yue M. Lu
AU - Subhabrata Sen
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05327
UR - https://arxiv.org/abs/2610.05327
AB - 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^⊤−I_d)/√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≤ 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).
ER -