Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929534402560000 |
|---|---|
| author | Montanari, Andrea Wein, Alexander S. |
| author_facet | Montanari, Andrea Wein, Alexander S. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06996 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation Montanari, Andrea Wein, Alexander S. Statistics Theory Probability 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. |
| title | Equivalence of Approximate Message Passing and Low-Degree Polynomials in Rank-One Matrix Estimation |
| topic | Statistics Theory Probability |
| url | https://arxiv.org/abs/2212.06996 |