Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.01522 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916985170821120 |
|---|---|
| author | Zhang, Anderson Ye |
| author_facet | Zhang, Anderson Ye |
| contents | We study the difference between the maximum likelihood estimation (MLE) and its semi-definite programming (SDP) relaxation for the phase synchronization problem, where $n$ latent phases are estimated based on pairwise observations corrupted by Gaussian noise at a level $σ$. While previous studies have established that SDP coincides with the MLE when $σ\lesssim \sqrt{n / \log n}$, the behavior in the high-noise regime $σ\gtrsim \sqrt{n / \log n}$ remains unclear. We address this gap by quantifying the deviation between the SDP and the MLE in the high-noise regime as $\exp(-c \frac{n}{σ^2})$, indicating an exponentially small discrepancy. In fact, we establish more general results for the Burer-Monteiro (BM) factorization that covers the SDP as a special case: it has the exponentially small deviation from the MLE in the high-noise regime and coincides with the MLE when $σ$ is small. To obtain our results, we develop a refined entrywise analysis of the MLE that is beyond the existing $\ell_\infty$ analysis in literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01522 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tightness of SDP and Burer-Monteiro Factorization for Phase Synchronization in High-Noise Regime Zhang, Anderson Ye Optimization and Control We study the difference between the maximum likelihood estimation (MLE) and its semi-definite programming (SDP) relaxation for the phase synchronization problem, where $n$ latent phases are estimated based on pairwise observations corrupted by Gaussian noise at a level $σ$. While previous studies have established that SDP coincides with the MLE when $σ\lesssim \sqrt{n / \log n}$, the behavior in the high-noise regime $σ\gtrsim \sqrt{n / \log n}$ remains unclear. We address this gap by quantifying the deviation between the SDP and the MLE in the high-noise regime as $\exp(-c \frac{n}{σ^2})$, indicating an exponentially small discrepancy. In fact, we establish more general results for the Burer-Monteiro (BM) factorization that covers the SDP as a special case: it has the exponentially small deviation from the MLE in the high-noise regime and coincides with the MLE when $σ$ is small. To obtain our results, we develop a refined entrywise analysis of the MLE that is beyond the existing $\ell_\infty$ analysis in literature. |
| title | Tightness of SDP and Burer-Monteiro Factorization for Phase Synchronization in High-Noise Regime |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.01522 |