Title:
Statistical estimation under group actions: The Sample Complexity of MultiReference Alignment
Abstract:
Many problems in signal/image processing, and computer vision amount to estimating a signal, image, or tridimensional 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
andorientations; CryoElectron Microscopy (CryoEM) imaging where projections of a molecule density are taken from unknown rotations,
andseveral others.
One fundamental example of this type of problems is MultiReference 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 signaltonoise 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.
