  Multi-reference alignment (MRA) is the problem of recovering a signal from
its multiple noisy copies, each acted upon by a random group element. MRA is
mainly motivated by single-particle cryo-electron microscopy (cryo-EM) that has
recently joined X-ray crystallography as one of the two leading technologies to
reconstruct biological molecular structures. Previous papers have shown that in
the high noise regime, the sample complexity of MRA and cryo-EM is
$n=\omega(\sigma^{2d})$, where $n$ is the number of observations, $\sigma^2$ is
the variance of the noise, and $d$ is the lowest-order moment of the
observations that uniquely determines the signal. In particular, it was shown
that in many cases, $d=3$ for generic signals, and thus the sample complexity
is $n=\omega(\sigma^6)$.
  In this paper, we analyze the second moment of the MRA and cryo-EM models.
First, we show that in both models the second moment determines the signal up
to a set of unitary matrices, whose dimension is governed by the decomposition
of the space of signals into irreducible representations of the group. Second,
we derive sparsity conditions under which a signal can be recovered from the
second moment, implying sample complexity of $n=\omega(\sigma^4)$. Notably, we
show that the sample complexity of cryo-EM is $n=\omega(\sigma^4)$ if at most
one third of the coefficients representing the molecular structure are
non-zero; this bound is near-optimal. The analysis is based on tools from
representation theory and algebraic geometry. We also derive bounds on
recovering a sparse signal from its power spectrum, which is the main
computational problem of X-ray crystallography.
