2025/05/27 by Amnon Balanov, Wasim Huleihel, Balanov, Amnon +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · #FOS: Electrical engineering #Gene expression and cancer classification #Genomics and Phylogenetic Studies #Machine Learning in Bioinformatics #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2505.21435
openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We study the multi-reference alignment (MRA) problem of recovering a signal from noisy observations acted on by unknown random circular shifts. While the information-theoretic limits of MRA are well characterized in many settings, the algorithmic behavior at low signal-to-noise ratio (SNR), the regime of practical interest, remains poorly understood. In this paper, we analyze the expectation-maximization (EM) algorithm, a widely used method for MRA, and characterize its convergence dynamics and initialization dependence in the low-SNR limit. On the convergence side, we prove a two-phase phenomenon near the ground truth as SNR→ 0: an initial contraction with error decaying as exp(- SNR ⋅ t) followed by a much slower phase scaling as exp(- SNR2 ⋅ t), where t is the iteration number. This yields an iteration-complexity lower bound T \gtrsim SNR-2 to reach a small fixed target accuracy, revealing a severe computational bottleneck at low SNR. We also identify a finite-sample instability, which we term Ghost of Newton, in which EM initially approaches the ground truth but later diverges, degrading reconstruction quality. On the bias side, we analyze EM in the noise-only setting (SNR=0), a regime referred to as Einstein from Noise, to highlight its pronounced sensitivity to initialization. We prove that the EM map preserves the Fourier phases of the initialization across all iterations, while the corresponding Fourier magnitudes contract toward zero at a slow rate of (1+T)-1/2. Consequently, although the amplitudes vanish in the limit of T → ∞ iterations, the reconstructed structure continues to reflect the geometry encoded by the template's Fourier phases. Together, these results expose fundamental computational and initialization-driven limitations of EM for MRA in the low-SNR regime.