TY - GEN

T1 - Multireference alignment using semidefinite programming

AU - Bandeira, Afonso S.

AU - Charikar, Moses

AU - Singer, Amit

AU - Zhu, Andy

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Multireference alignment

KW - Phase correlation

KW - Semidefinite relaxation

KW - Unique-games

UR - http://www.scopus.com/inward/record.url?scp=84893326664&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893326664&partnerID=8YFLogxK

U2 - 10.1145/2554797.2554839

DO - 10.1145/2554797.2554839

M3 - Conference contribution

AN - SCOPUS:84893326664

SN - 9781450322430

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

SP - 459

EP - 470

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

PB - Association for Computing Machinery

T2 - 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014

Y2 - 12 January 2014 through 14 January 2014

ER -