Learning under group actions: The sample complexity of Multi-reference Alignment

Many problems in signal/image processing, and computer vision amount to estimating a signal, image, or tri-dimensional structure/scene from corrupted measurements. A particularly challenging form of measurement corruption are latent transformations of the underlying signal to be recovered. Examples include the Simulatenous Localization and Mapping (SLaM) problem in Robotics and Computer Vision, where pictures of a scene are obtained from different positions and orientations, Cryo-Electron Microscopy (Cryo-EM) imaging where projections of a molecule density are taken from unknown rotations, and several others.

One fundamental example of this type of problems is Multi-reference Alignment: in one of its simplest forms the goal is to estimate a signal from noisy cyclically shifted copies. We will show that the number of observations needed has a surprising dependency on the signal-to-noise ratio (SNR), and algebraic properties of the underlying group action. Remarkably, in some important cases, this sample complexity is achieved with computationally efficient methods based on computing invarants under the group of transformations.

We will also discuss the sample complexity of the heterogeneous multi-reference alignment problem where the samples come from a mixture of signals, and provide the first known procedure that provably achieves signal recovery in the low SNR regime. A related problem is heterogenous reconstruction in Cryo-Electron Microscopy (Cryo-EM) imaging where multiple unknown molecules or molecules in multiple unknowm conformations are imaged together. Our work can be seen as a first step towards a complete statistical theory of heterogenous Cryo-EM.