Relaxing is not the end of it

Speaker: 
Nicolas Boumal
Date: 
Apr 18 2013 - 3:45pm
Event type: 
IDeAS
Room: 
102A McDonnell Hall
Abstract: 

Synchronization of rotations is the problem of estimating a set of rotations from measurements of pairwise relative rotations. Several convex relaxations of this problem have been proposed. These relaxations enjoy excellent theoretical performance guarantees. The relaxation approaches involve a final projection step, that brings back the solution of the relaxed problem to the original feasible set. This projection step though does not, in general, provide even a local optimizer of the original problem. In this presentation, I will argue that relaxing is not the end of it: further reaching for a critical point of the problem we actually want to solve can make a big difference. Indeed, the algorithm we propose appears to be efficient, as compared to fundamental Cramér-Rao bounds. If time allows, I will present Manopt, a matlab toolbox for optimization on manifolds. This is the toolbox we use to perform the nonlinear optimization step that follows the projection step in synchronization. Such a toolbox is of interest to refine relaxed solutions in a wide range of applications. Joint work with Amit Singer and Pierre-Antoine Absil.