# Multi-reference alignment in high dimensions: sample complexity and phase transition

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2020.

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

- [Sparse Multi-Reference Alignment : Phase Retrieval, Uniform Uncertainty Principles and the Beltway Problem](https://mlsanity.com/paper/2106.12996/) (2021)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [Multi-target detection with rotations](https://mlsanity.com/paper/2101.07709/) (2021)
- [An accelerated expectation-maximization algorithm for multi-reference alignment](https://mlsanity.com/paper/2105.07372/) (2021)
- [Unrolled algorithms for group synchronization](https://mlsanity.com/paper/2207.09418/) (2022)

## Abstract (arXiv)

Multi-reference alignment entails estimating a signal in ℝL from its circularly-shifted and noisy copies. This problem has been studied thoroughly in recent years, focusing on the finite-dimensional setting (fixed L). Motivated by single-particle cryo-electron microscopy, we analyze the sample complexity of the problem in the high-dimensional regime L→∞. Our analysis uncovers a phase transition phenomenon governed by the parameter α = L/(σ2log L), where σ2 is the variance of the noise. When α>2, the impact of the unknown circular shifts on the sample complexity is minor. Namely, the number of measurements required to achieve a desired accuracy varepsilon approaches σ2/varepsilon for small varepsilon; this is the sample complexity of estimating a signal in additive white Gaussian noise, which does not involve shifts. In sharp contrast, when α≤ 2, the problem is significantly harder and the sample complexity grows substantially quicker with σ2.