Brown University shieldBrown University

The Sample Complexity of Multi-Reference Alignment

The Sample Complexity of Multi-Reference Alignment

Philippe Rigollet, MIT

How should one estimate a signal, given only access to noisy versions of the signal corrupted by unknown cyclic shifts? This simple problem has surprisingly broad applications, in fields from structural biology to aircraft radar imaging. We describe how this model can be viewed as a multivariate Gaussian mixture model whose centers belong to an orbit of a group of orthogonal transformations. This enables us to derive matching lower and upper bounds for the optimal rate of statistical estimation for the underlying signal. These bounds show a striking dependence on the signal-to-noise ratio of the problem. We also show how a tensor based method of moments can solve the problem efficiently.

Joint work with Afonso Bandeira (NYU) and Jonathan Weed (MIT).