Multireference Alignment via Convex Optimization

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.