arXiv preprint ·
Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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).
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Entanglement-of-formation potentials for feedback-assisted classical communication and randomness distillation
SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints
Quantum codes in the Lee metric
The Arbitrary-Placement Problem in Entropy-Minimizing Selection, and a Residual-Entropy Formulation
A Contrast-Source Inversion Scheme Based on Stochastic Optimization and Plug-and-Play Regularization
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.