10 Lectures and 42 Open Problems — Angular Synchronization via Projected Power Method
Let have for every , and observe the Hermitian matrix
where , , and, for , the entries are independent standard complex Gaussian random variables, with . The angular synchronization estimator is a solution of
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 , where acts entrywise by for and . The lecture poses the question of which noise levels make this iteration converge with high probability to an optimizer, or at least to a vector correlated with . 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 from noisy measurements of their pairwise offsets; representing each angle by turns an offset into the phase ratio . The problem is an instance of synchronization over the rotation group 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
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.