Multireference Alignment via Convex Optimization

Speaker: 
Andy Zhu
Date: 
Apr 2 2013 - 12:30pm
Event type: 
Graduate Student Seminar
Room: 
601 Fine Hall
Abstract: 

The multireference alignment problem consists of estimating a signal from noisy shifted observations of it. If the shifts were known one could simply shift back each observation, and then average to diminish the noise. However, in relevant applications, the shifts are unknown.
We present several methods to estimate the unknown shifts and the signal. Our main contribution is an poly-time approximation algorithm to solve this problem inspired by a certain semidefinite programming based approach to the Unique Games problem, which seems to have comparable performance to the (computationally hard) maximum likelihood estimator. We also mention how we can leverage recent results about symmetry reduction in semidefinite programs from representation theory. Joint work with A. S. Bandeira, M. Charikar, and A. Singer.