Solving Group Synchronization via Optimization and Spectral Methods



Shuyang Ling, New York University


2020.10.15 10:00-11:00




Conference ID: 945-021-74117
PIN Code: 837316


Group synchronization aims to recover the group elements from their noisy pairwise measurements. It has found numerous applications in community detection, clock synchronization, and joint alignment problem. In this talk, we will focus on the orthogonal group synchronization which is often used in cryo-EM and computer vision. However, it is generally NP-hard to retrieve the group elements by finding the least squares estimator. We will introduce three different approaches to tackle the orthogonal group synchronization: convex relaxation, fast first-order method such as Burer-Monteiro factorization, and spectral methods. We will discuss several aspects of theoretical and algorithmic advances (a) when is convex relaxation tight, meaning the solution from convex relaxation is exactly the global optimal solution; (b) when does nonconvex approach work? We will understand how the optimization landscape depends on the signal-to-noise ratio; (c) when do simple spectral methods work and is it optimal in terms of information theoretical limits? Numerical experiments will be provided to complement our analysis and future directions will be discussed.


Dr. Shuyang Ling is a tenure-track Assistant Professor of Data Science at New York University Shanghai and NYU Global Network Assistant Professor. From 2017 to 2019, he was an Assistant Professor/Courant Instructor at Courant Institute of Mathematical Sciences (CIMS) and Center for Data Science. He received his PhD in Mathematics at University of California, Davis, supervised by Prof. Thomas Strohmer. His research interest includes optimization, inverse problems, random matrix theory, computational harmonic analysis, spectral graph theory, spectral methods and many others. He is currently co-organizing the online One World Mathematics of INformation, Data, and Signals (MINDS) Seminar.