Multi-reference alignment in high dimensions: sample complexity and phase transition
This addresses the sample complexity challenge in multi-reference alignment for applications like cryo-electron microscopy, providing theoretical insights but is incremental as it extends prior finite-dimensional analysis to high dimensions.
The paper tackles the problem of estimating a signal from its noisy and circularly-shifted copies in high dimensions, revealing a phase transition where sample complexity is minor when α>2 but grows substantially when α≤2, with specific thresholds like α=2 governing the transition.
Multi-reference alignment entails estimating a signal in $\mathbb{R}^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\to\infty$. Our analysis uncovers a phase transition phenomenon governed by the parameter $α= L/(σ^2\log 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 $α\leq 2$, the problem is significantly harder and the sample complexity grows substantially quicker with $σ^2$.