Phase synchronization: an example of global optimality on manifolds (Nicolas Boumal - Inria & ENS Paris)

15.12.2015 14:15 – 15:00

I will talk about the problem of estimating n phases (angles) based on noisy, pairwise relative phase measurements. Under a Gaussian noise model, computing the maximum likelihood estimator (MLE) is, in general, an NP-hard problem. in contrast; we show that, if the noise level is sufficiently small, then, with high probability, the MLE can be obtained as the unique solution of a semidefinite program, which can be solved in polynomial time. Furthermore, we show that efficient algorithms based on Riemannian optimization can solve the semidefinite program quite fast (faster than off-the-shelf methods for semidefinite programming). This is both an example of a problem which is hard in general but tractable in practice, and an example of fruitful interaction between convex optimization and Riemannian optimization.

This is joint work with Afonso Bandeira and Amit Singer. Details are in this paper: http://arxiv.org/abs/1411.3272

Lieu

salle 623, Séminaire d'analyse numérique

entrée libre