Conference Global Portuguese Mathematicians 

14/07/2017, 09:30 — 10:30 — Amphitheatre Pa1, Mathematics Building
Afonso Bandeira, New York University

Statistical estimation 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. Many such transformations can be described as a group acting on the object 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: Given a group acting in a space, the goal is to estimate an orbit of the group action from noisy samples. For example, in one of its simplest forms, one is tasked with estimating a signal from noisy cyclically shifted copies. We will show that the number of observations needed by any method 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 invariants 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 unknown conformations are imaged together. Our work can be seen as a first step towards a complete statistical theory of heterogenous Cryo-EM.