Multi-reference alignment in high dimensions: sample complexity and phase transition
arXiv:2007.11482 · doi:10.1137/20M1354994
Abstract
Multi-reference alignment entails estimating a signal in from its circularly-shifted and noisy copies. This problem has been studied thoroughly in recent years, focusing on the finite-dimensional setting (fixed ). Motivated by single-particle cryo-electron microscopy, we analyze the sample complexity of the problem in the high-dimensional regime . Our analysis uncovers a phase transition phenomenon governed by the parameter , where is the variance of the noise. When , the impact of the unknown circular shifts on the sample complexity is minor. Namely, the number of measurements required to achieve a desired accuracy approaches for small ; this is the sample complexity of estimating a signal in additive white Gaussian noise, which does not involve shifts. In sharp contrast, when , the problem is significantly harder and the sample complexity grows substantially quicker with .
References in corpus (7)
- Nonconvex phase synchronization
- Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities
- Bispectrum Inversion with Application to Multireference Alignment
- Denoising and Covariance Estimation of Single Particle Cryo-EM Images
- Message-passing algorithms for synchronization problems over compact groups
- Method of moments for 3-D single particle ab initio modeling with non-uniform distribution of viewing angles
- The Noise-Sensitivity Phase Transition in Spectral Group Synchronization Over Compact Groups