To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr17f02
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Zhong, Yiqiao | - |
dc.contributor.author | Boumal, Nicolas | - |
dc.date.accessioned | 2019-08-29T17:02:00Z | - |
dc.date.available | 2019-08-29T17:02:00Z | - |
dc.date.issued | 2018 | en_US |
dc.identifier.citation | Zhong, Yiqiao, Boumal, Nicolas. (2018). NEAR-OPTIMAL BOUNDS FOR PHASE SYNCHRONIZATION. SIAM JOURNAL ON OPTIMIZATION, 28 (989 - 1016. doi:10.1137/17M1122025 | en_US |
dc.identifier.issn | 1052-6234 | - |
dc.identifier.uri | http://arks.princeton.edu/ark:/88435/pr17f02 | - |
dc.description.abstract | The problem of estimating the phases (angles) of a complex unit-modulus vector z from their noisy pairwise relative measurements C = zz* + sigma W, where W is a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unitmodulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite programming (SDP) relaxation or the generalized power method (GPM). Numerical experiments suggest that both of these methods succeed with high probability for sigma up to <(O)overtilde>(n(1/2)), yet existing analyses only confirm this observation for sigma up to <(O)overtilde>(n(1/2)). In this paper, we bridge the gap by proving that the SDP relaxation is tight for sigma = O(root n/log n), and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter l(infinity) bound for the MLE. A novel technique we develop in this paper is to (theoretically) track n closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an l(infinity) perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics. | en_US |
dc.format.extent | 989 - 1016 | en_US |
dc.language.iso | en_US | en_US |
dc.relation.ispartof | SIAM JOURNAL ON OPTIMIZATION | en_US |
dc.rights | Final published version. Article is made available in OAR by the publisher's permission or policy. | en_US |
dc.title | NEAR-OPTIMAL BOUNDS FOR PHASE SYNCHRONIZATION | en_US |
dc.type | Journal Article | en_US |
dc.identifier.doi | doi:10.1137/17M1122025 | - |
dc.date.eissued | 2018-04-03 | en_US |
dc.identifier.eissn | 1095-7189 | - |
pu.type.symplectic | http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article | en_US |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
17m1122025.pdf | 491.7 kB | Adobe PDF | View/Download |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.