Codes and Expansions (CodEx) Seminar

Dan Edidin (University of Missouri):
The second moment and the sparse multi-reference alignment problem

Given a representation of a compact Lie group, the second moment of a signal vector can be viewed as a representation-theoretic generalization of the power spectrum in Fourier theory where the group is \(S^1\). In this talk I'll describe the information determined by the second moment and use it to derive sparsity conditions under which a signal can be recovered from its second moment. Multi-reference alignment (MRA) is the problem of recovering a signal from multiple noisy random group translates. In the high noise regime, the sample complexity (number of measurements required for accurate approximation) is \(\omega (\sigma ^{2d})\) where \(\sigma ^2\) is the variance of the noise and \(d\) is the smallest degree moment which uniquely determines the vector, and our result gives conditions which ensures that the sample complexity is \(\omega (\sigma ^4)\). MRA is mainly motivated by single-particle cryo-electron microscopy (cryo-EM) where the group is \(SO(3)\) acting on \(L^2(\mathbb{R}^3)\). Using our results we show that the sample complexity of cryo-EM is \(\omega (\sigma ^4)\) if at most one third of the coefficients representing the molecular structure in a suitable basis are non-zero - which near-optimal.

This is based on joint work with Tamir Bendory.