Multireference alignment using semidefinite programming

Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

The multireference alignment problem consists of estimating a signal from multiple noisy shifted observations. Inspired by existing Unique-Games approximation algorithms, we provide a semidefinite program (SDP) based relaxation which approximates the maximum likelihood estimator (MLE) for the multireference alignment problem. Although we show this MLE problem is Unique-Games hard to approximate within any constant, we observe that our poly-time approximation algorithm for this problem appears to perform quite well in typical instances, outperforming existing methods. In an attempt to explain this behavior we provide stability guarantees for our SDP under a random noise model on the observations. This case is more challenging to analyze than traditional semi-random instances of Unique-Games: the noise model is on vertices of a graph and translates into dependent noise on the edges. Interestingly, we show that if certain positivity constraints in the relaxation are dropped, its solution becomes equivalent to performing phase correlation, a popular method used for pairwise alignment in imaging applications. Finally, we describe how symmetry reduction techniques from matrix representation theory can greatly decrease the computational cost of the SDP considered.

Original languageEnglish (US)
Title of host publicationITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery
Pages459-470
Number of pages12
ISBN (Print)9781450322430
DOIs
StatePublished - Jan 1 2014
Event2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States
Duration: Jan 12 2014Jan 14 2014

Publication series

NameITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

Other

Other2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
CountryUnited States
CityPrinceton, NJ
Period1/12/141/14/14

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Keywords

  • Multireference alignment
  • Phase correlation
  • Semidefinite relaxation
  • Unique-games

Fingerprint Dive into the research topics of 'Multireference alignment using semidefinite programming'. Together they form a unique fingerprint.

  • Cite this

    Bandeira, A. S., Charikar, M., Singer, A., & Zhu, A. (2014). Multireference alignment using semidefinite programming. In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (pp. 459-470). (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery. https://doi.org/10.1145/2554797.2554839