论文标题
在等级矩阵估计中，近似消息传递和低度多项式的等效性
Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation
论文作者
论文摘要
我们考虑估计未知参数向量$ {\boldsymbolθ} \ in {\ mathbb r}^n $，给定噪声观察$ {\ boldsymbol y} = {\ boldSymbolthsy z} $ rank-One矩阵$ {\boldsymbolθ} {\boldsymbolθ}}^{\ top} $，其中$ {\ boldsymbol z} $具有独立的高斯条目。当有有关$ {\boldsymbolθ} $条目的分布的信息时，众所周知，光谱方法是严格的次级优势。过去的工作表征了最佳估计器达到的准确性的渐近学。但是，尚无多项式时间估计器可以达到这种准确性。 已经猜想这一统计计算差距是基本的，而且多项式时间估计器可实现的最佳精度与通过某些近似消息传递（AMP）算法获得的准确性相吻合。我们通过证明（更广泛的）恒定程度多项式中没有估计器可以超过AMP，从而为这种猜想提供了证据。
We consider the problem of estimating an unknown parameter vector ${\boldsymbol θ}\in{\mathbb R}^n$, given noisy observations ${\boldsymbol Y} = {\boldsymbol θ}{\boldsymbol θ}^{\top}/\sqrt{n}+{\boldsymbol Z}$ of the rank-one matrix ${\boldsymbol θ}{\boldsymbol θ}^{\top}$, where ${\boldsymbol Z}$ has independent Gaussian entries. When information is available about the distribution of the entries of ${\boldsymbol θ}$, spectral methods are known to be strictly sub-optimal. Past work characterized the asymptotics of the accuracy achieved by the optimal estimator. However, no polynomial-time estimator is known that achieves this accuracy. It has been conjectured that this statistical-computation gap is fundamental, and moreover that the optimal accuracy achievable by polynomial-time estimators coincides with the accuracy achieved by certain approximate message passing (AMP) algorithms. We provide evidence towards this conjecture by proving that no estimator in the (broader) class of constant-degree polynomials can surpass AMP.
