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

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.