{"ID":2862379,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.01522","arxiv_id":"2510.01522","title":"Tightness of SDP and Burer-Monteiro Factorization for Phase Synchronization in High-Noise Regime","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2510.01522","url_pdf":"https://arxiv.org/pdf/2510.01522v1","authors":"[\"Anderson Ye Zhang\"]","published":"2025-10-01T23:38:11Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}