← All problems

10 Lectures and 42 Open Problems — Angular Synchronization via Projected Power Method

Let z∈Cnz\in\mathbb{C}^n have ∣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, Wii=0W_{ii}=0, and, for i<ji<j, the entries WijW_{ij} are independent standard complex Gaussian random variables, with Wji=Wij‾W_{ji}=\overline{W_{ij}}. The angular synchronization estimator is a solution of

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\ (i=1,\ldots,n).

The global phase of a feasible vector does not affect this objective, so solutions are understood up to multiplication by a scalar of modulus one. Near-optimal bounds for phase synchronization MIT OCW, Fall 2015 lecture notes

The projected power iteration is xt+1=P(Cxt)x^{t+1}=\mathcal{P}(Cx^t), where P\mathcal{P} acts entrywise by P(a)=a/∣a∣\mathcal{P}(a)=a/|a| for a≠0a\ne0 and P(0)=1\mathcal{P}(0)=1. The lecture poses the question of which noise levels σ\sigma make this iteration converge with high probability to an optimizer, or at least to a vector correlated with zz. Its description allows an initial vector that may be random but does not specify a distribution for it; results below therefore state their initialization assumptions explicitly. Near-optimal bounds for phase synchronization MIT OCW, Fall 2015 lecture notes

Background

Angular synchronization asks for unknown angles θi\theta_i from noisy measurements of their pairwise offsets; representing each angle by zi=eiθiz_i=e^{i\theta_i} turns an offset into the phase ratio zizj‾z_i\overline{z_j}. The problem is an instance of synchronization over the rotation group SO(2)SO(2) and arises, among other settings, in clock synchronization, phase retrieval, and surface reconstruction. Singer’s 2011 work treated angular synchronization using eigenvectors and semidefinite programming. The 2015 lecture presented projected power iteration as a simple alternative to spectral relaxation followed by a single rounding step, and identified its analysis under the stated Gaussian model as an open problem; it credits Nicolas Boumal with suggesting the question. MIT OCW, Fall 2015 lecture notes

The basic mechanism is to multiply by the observed matrix, which incorporates information from all pairwise measurements, then project each coordinate back to the unit circle. This differs from ordinary power iteration followed by rounding only once: the projection is applied at every step. The distinction matters for the guarantees, which depend on the initialization and on the precise projected or generalized iteration being analyzed. MIT OCW, Fall 2015 lecture notes Near-optimal bounds for phase synchronization

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.