Minimax-optimal estimation for sparse multi-reference alignment with
  collision-free signals
Subhro Ghosh Soumendu Sundar Mukherjee Jing Bin Pan
The Multi-Reference Alignment (MRA) problem aims at the recovery of an
unknown signal from repeated observations under the latent action of a group of
cyclic isometries, in the presence of additive noise of high intensity
$\sigma$. It is a more tractable version of the celebrated cryo EM model. In
the crucial high noise regime, it is known that its sample complexity scales as
$\sigma^6$. Recent investigations have shown that for the practically
significant setting of sparse signals, the sample complexity of the maximum
likelihood estimator asymptotically scales with the noise level as $\sigma^4$.
In this work, we investigate minimax optimality for signal estimation under the
MRA model for so-called collision-free signals. In particular, this signal
class covers the setting of generic signals of dilute sparsity (wherein the
support size $s=O(L^{1/3})$, where $L$ is the ambient dimension.
  We demonstrate that the minimax optimal rate of estimation in for the sparse
MRA problem in this setting is $\sigma^2/\sqrt{n}$, where $n$ is the sample
size. In particular, this widely generalizes the sample complexity asymptotics
for the restricted MLE in this setting, establishing it as the statistically
optimal estimator. Finally, we demonstrate a concentration inequality for the
restricted MLE on its deviations from the ground truth.