{"id":"arxiv/2609.06988","url":"https://arxiv.org/abs/2609.06988","tags":["math.ST","cs.DS","math.PR"],"score":0,"title":"Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials","domain":"math.ST","source":"arxiv","authors":["Zhangsong Li"],"reviews":0,"subject":"math.ST","summary":"We prove a sharp lower bound for growing-degree polynomial estimation in the symmetric rank-one matrix estimation problem. The observation is \\[ \\boldsymbol{Y}=\\frac{1}{\\sqrt{n}} \\boldsymbolθ \\boldsymbolθ^{\\top}+\\boldsymbol{W}, \\] where the coordinates of $\\boldsymbolθ$ are independent with a common, fixed sub-Gaussian distribution $π_Θ$ satisfying $\\mathbb E[Θ]\\neq0$, and $\\boldsymbol{W}$ is symmetric with independent standard Gaussian upper-triangular entries. For every such prior, we give an explicit finite-dimensional bound implying that every sequence of polynomial estimators of degree…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}