Summary
This paper studies how well certain polynomial techniques can estimate a hidden pattern inside a noisy large matrix, where the pattern is formed by random Bernoulli variables. The authors prove a precise lower bound on the error for polynomial methods whose degree grows slowly with the matrix size, showing they cannot outperform a known algorithm called approximate message passing (AMP). They build on previous results for fixed-degree polynomials and link growing-degree polynomial performance exactly to AMP’s performance. To do this, they use a new technical tool involving conditional joint cumulants and an auxiliary Gaussian channel related to the AMP fixed point, enabling fine control of errors as the polynomial degree increases.
Gaussian planted submatrix modelBernoulli random variablesapproximate message passing (AMP)polynomial estimatorsmean-square errorBayes estimationlow-degree polynomialsjoint cumulantsGaussian noisestatistical signal detection
Abstract
We prove a sharp lower bound for growing-degree polynomial estimation in the Gaussian planted submatrix model. The observation is $$ \boldsymbol{Y}= \fracλ{\sqrt{n}} \boldsymbolθ \boldsymbolθ^{\top}+\boldsymbol{W}, $$ where the coordinates of $\boldsymbolθ$ are independent $\mathsf{Ber}(ρ)$ variables and $\boldsymbol{W}$ is symmetric with independent standard Gaussian upper-triangular entries. For every fixed $λ>0$ and $ρ\in(0,1)$, we give an explicit finite-dimensional bound implying that every sequence of polynomial estimators of degree $D(n)=o(n^{1/60})$ has normalized mean-square error with limit inferior at least $ρ-q_{\mathsf{amp}}/λ$, the limiting error of Bayes approximate message passing (AMP). This extends the constant-degree result of Montanari and Wein~\cite{montanari2025equivalence} for the Bernoulli prior. Combined with their polynomial approximation of fixed-iteration AMP, the bound identifies the exact limiting low-degree MMSE whenever $D(n)\to\infty$ within this range. It therefore resolves the Bernoulli rank-one case of the growing-degree AMP-equivalence question discussed in~\cite{wein2025computational, maleki2026high}. The proof constructs a low-degree certificate using \emph{conditional} joint cumulants of the signal coordinates and their products. Specifically, we condition on an auxiliary Gaussian channel $\boldsymbol{R}$ calibrated to the AMP fixed point. This retains signal dependence that is lost in unconditional cumulant bounds and produces the cancellations needed for quantitative control as the degree grows. Most of the arguments in this paper were generated using GPT-6 Astra.