Imaging and Computing Seminar

Nicolas Boumal, ICTEAM, UCL Belgium

Relax, project and refine: accurate and robust estimation of rotations from relative measurements

Synchronization of rotations is the problem of estimating a set of rotations from measurements of pairwise relative rotations. This basic problem appears for example in Cryo-EM imaging, structure from motion or registration of networks of cameras. Several convex (or otherwise tractable) relaxations of this problem have been proposed. These relaxations enjoy excellent theoretical performance guarantees. The relaxation approaches involve a final projection step, that brings the solution of the relaxed problem back to the original feasible set. However, this projection step does not, in general, provide an (even local) optimizer of the original problem. I will argue that relaxing is not the end of the story: further reaching for a critical point of the problem we actually want to solve can make a big difference. We do so using optimization on manifolds. The algorithm we propose appears to be efficient, as compared to fundamental Cramer-Rao bounds we derive, and is able to reject an overwhelming majority of outliers. If time allows, I will present Manopt, the matlab toolbox for optimization on manifolds we use to refine the projected solution. Such a toolbox is of interest to refine relaxed solutions in a wide range of applications.

Joint work with Amit Singer (Princeton University) and Pierre-Antoine Absil (Universite catholique de Louvain).