# Multireference Alignment using Semidefinite Programming

arXiv: https://arxiv.org/abs/1308.5256 · HTML: https://mlsanity.com/paper/1308.5256/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Aug 2013.

## Built on by (most cited first, 10 of 10)

- [Learning Sheaf Laplacian Optimizing Restriction Maps](https://mlsanity.com/paper/2501.19207/) (2025)
- [Sparse Multi-Reference Alignment : Phase Retrieval, Uniform Uncertainty Principles and the Beltway Problem](https://mlsanity.com/paper/2106.12996/) (2021)
- [An accelerated expectation-maximization algorithm for multi-reference alignment](https://mlsanity.com/paper/2105.07372/) (2021)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)
- [Unrolled algorithms for group synchronization](https://mlsanity.com/paper/2207.09418/) (2022)
- [Distinguishing Cause from Effect on Categorical Data: The Uniform Channel Model](https://mlsanity.com/paper/2303.08572/) (2023)
- [Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models](https://mlsanity.com/paper/2305.06704/) (2023)
- [Dictionary Learning under Symmetries via Group Representations](https://mlsanity.com/paper/2305.19557/) (2023)
- [Minimax-optimal estimation for sparse multi-reference alignment with collision-free signals](https://mlsanity.com/paper/2312.07839/) (2023)
- [Orientation Estimation of Cryo-EM Images for Molecules with Arbitrary Symmetry by Semidefinite Programming](https://mlsanity.com/paper/2610.18691/) (2026)

## Abstract (arXiv)

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 that the MLE problem is Unique-Games hard to approximate within any constant, we observe that our poly-time approximation algorithm for the MLE 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 SDP are dropped, its solution becomes equivalent to performing phase correlation, a popular method used for pairwise alignment in imaging applications. Finally, we show how symmetry reduction techniques from matrix representation theory can simplify the analysis and computation of the SDP, greatly decreasing its computational cost.