10 Lectures and 42 Open Problems — Sharp tightness of the Angular Synchronization SDP
Let , let be a vector with for every , and observe the Hermitian matrix
where and has zero diagonal and independent standard complex Gaussian entries above the diagonal, with . The angular-synchronization maximum-likelihood problem is
and its semidefinite relaxation is
The relaxation is tight when it has an optimal solution of rank one, , with a global optimizer of the constrained problem. The question is whether, with high probability as grows, tightness persists for noise levels essentially up to the point at which the solution of angular synchronization ceases to correlate with the planted vector . The question does not specify a correlation metric or a precise meaning of “essentially until”; those features are therefore part of the proposed sharp-threshold direction, not additional hypotheses imposed here. Bandeira, Ten Lectures and Forty-Two Open Problems (2016) Bandeira, Boumal, and Singer (2015)
Background
Angular synchronization estimates phases from noisy pairwise relative-phase measurements. It arises in settings including time synchronization, ranking, phase retrieval, and surface reconstruction, and serves as a basic model for synchronization problems involving rotations. The likelihood objective is a nonconvex quadratic optimization over unit-modulus vectors; in general, this problem is NP-hard. Lifting to its Gram matrix makes the objective linear and yields the SDP by dropping the rank-one constraint. Thus tightness means more than obtaining an approximation: it certifies that the convex program recovers a global maximum-likelihood solution, though that estimator need not equal the planted phases. Bandeira, Boumal, and Singer (2015)
The striking feature motivating the question is that exact recovery of the planted signal can fail while the SDP still computes the maximum-likelihood estimator exactly. The 2015 work established this phenomenon in a Gaussian model and noted that numerical experiments suggested tightness at substantially larger noise levels than its theorem could prove. Bandeira’s 2016 open-problems notes then posed the sharper question of whether tightness lasts essentially until correlation with the ground truth is lost. Bandeira, Boumal, and Singer (2015) Bandeira, Ten Lectures and Forty-Two Open Problems (2016)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.