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

Code

• github.com/TamirBendory/high-dimensional-mra-bounds
  OfficialIn papernone★ 0

Abstract

Multi-reference alignment entails estimating a signal in 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. Our analysis uncovers a phase transition phenomenon governed by the parameter = L/(^2 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 approaches ^2/ 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 2, the problem is significantly harder and the sample complexity grows substantially quicker with ^2.

Tasks

Reproductions