← All problems

10 Lectures and 42 Open Problems — Sharp tightness of the Angular Synchronization SDP

Let n≥2n\ge 2, let z∈Cnz\in\mathbb C^n be a vector with ∣zi∣=1|z_i|=1 for every ii, and observe the Hermitian matrix

C=zz∗+σW,C=zz^*+\sigma W,

where σ≥0\sigma\ge 0 and WW has zero diagonal and independent standard complex Gaussian entries above the diagonal, with Wji=Wij‾W_{ji}=\overline{W_{ij}}. The angular-synchronization maximum-likelihood problem is

max⁡x∈Cn x∗Cxsubject to ∣xi∣=1(i=1,…,n),\max_{x\in\mathbb C^n}\ x^*Cx\quad\text{subject to }|x_i|=1\quad(i=1,\ldots,n),

and its semidefinite relaxation is

max⁡X∈Cn×n Tr⁡(CX)subject to X=X∗,diag⁡(X)=1,X⪰0.\max_{X\in\mathbb C^{n\times n}}\ \operatorname{Tr}(CX) \quad\text{subject to }X=X^*,\quad \operatorname{diag}(X)=\mathbf 1,\quad X\succeq0.

The relaxation is tight when it has an optimal solution of rank one, X=xx∗X=xx^*, with xx a global optimizer of the constrained problem. The question is whether, with high probability as nn 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 zz. 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 xx to its Gram matrix xx∗xx^* 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)

References

Progress summary

Never refreshed

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.