The last set of Lecture notes for my course are now available here and are about Synchronization problems. They also include the last four open problems of the course. I will document the open problems here, while referring a much more detailed description of the problems on the notes, including description of partial progress.
Open Problem 10.1. (Angular Synchronization via Projected Power Method)
Does the projected power method converge (with high probability) to the optimal solution of the angular synchronization problem with (small enough) gaussian noise?
Open Problem 10.2. (Sharp tightness of the Angular Synchronization SDP)
Is the SDP for angular synchronization tight (with high probability) for noise levels
essentially until the solution of angular synchronization no longer correlates with the ground truth?
Open Problem 10.3. (Tightness of the Multireference Alignment SDP)
For which levels of noise is the SDP for Multireference Alignment tight?
Open Problem 10.4. (Consistency and sample complexity of Multireference Alignment)
- Is the Maximum likelihood for Multireference Alignment consistent? (after fixing the power spectrum)
- What is the sample complexity of the Multireference Alignment problem?
Relax and Conquer 