  The growing role of data-driven approaches to scientific discovery has
unveiled a large class of models that involve latent transformations with a
rigid algebraic constraint. Three-dimensional molecule reconstruction in
Cryo-Electron Microscopy (cryo-EM) is a central problem in this class. Despite
decades of algorithmic and software development, there is still little
theoretical understanding of the sample complexity of this problem, that is,
number of images required for 3-D reconstruction. Here we consider
multi-reference alignment (MRA), a simple model that captures fundamental
aspects of the statistical and algorithmic challenges arising in cryo-EM and
related problems. In MRA, an unknown signal is subject to two types of
corruption: a latent cyclic shift and the more traditional additive white
noise. The goal is to recover the signal at a certain precision from
independent samples. While at high signal-to-noise ratio (SNR), the number of
observations needed to recover a generic signal is proportional to
$1/\mathrm{SNR}$, we prove that it rises to a surprising $1/\mathrm{SNR}^3$ in
the low SNR regime. This precise phenomenon was observed empirically more than
twenty years ago for cryo-EM but has remained unexplained to date. Furthermore,
our techniques can easily be extended to the heterogeneous MRA model where the
samples come from a mixture of signals, as is often the case in applications
such as cryo-EM, where molecules may have different conformations. This
provides a first step towards a statistical theory for heterogeneous cryo-EM.
