Seminar Details
2023-11-27 (11h) : Benign nonconvexity in group synchronization and graph clustering
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Andrew McRae (EPFL)
Abstract :
I consider an optimization problem arising in orthogonal group synchronization, in which we seek to estimate orthogonal matrices from (noisy) relative measurements. The least-squares estimator over orthogonal matrices is a nonconvex program that, in general, has many spurious local minima. We show that adding a small number of degrees of freedom (specifically, relaxing to optimization over slightly “wider” Stiefel manifold matrices) makes the nonconvexity benign and still yields an optimal solution to the original problem. The general matrix case is studied in our preprint. Time permitting, I will discuss how these results can be strengthened for $Z_2$ synchronization and can be extended to the graph clustering problem under the stochastic block model; our nonconvex approach yields exact recovery for these problems up to the information-theoretic SNR threshold.