Heterogeneous multireference alignment: A single pass approach

Nicolas Boumal, Tamir Bendory, Roy R. Lederman, Amit Singer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

Multireference alignment (MRA) is the problem of estimating a signal from many noisy and cyclically shifted copies of itself. In this paper, we consider an extension called heterogeneous MRA, where K signals must be estimated, and each observation comes from one of those signals, unknown to us. This is a simplified model for the heterogeneity problem notably arising in cryo-electron microscopy. We propose an algorithm which estimates the K signals without estimating either the shifts or the classes of the observations. It requires only one pass over the data and is based on low-order moments that are invariant under cyclic shifts. Given sufficiently many measurements, one can estimate these invariant features averaged over the K signals. We then design a smooth, non-convex optimization problem to compute a set of signals which are consistent with the estimated averaged features. We find that, in many cases, the proposed approach estimates the set of signals accurately despite non-convexity, and conjecture the number of signals K that can be resolved as a function of the signal length L is on the order of √L.

Original languageEnglish (US)
Title of host publication2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-6
Number of pages6
ISBN (Electronic)9781538605790
DOIs
StatePublished - May 21 2018
Event52nd Annual Conference on Information Sciences and Systems, CISS 2018 - Princeton, United States
Duration: Mar 21 2018Mar 23 2018

Publication series

Name2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018

Other

Other52nd Annual Conference on Information Sciences and Systems, CISS 2018
CountryUnited States
CityPrinceton
Period3/21/183/23/18

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Information Systems

Keywords

  • Gaussian mixture models
  • Multireference alignment
  • bispectrum
  • cryo-EM
  • expectation-maximization
  • heterogeneity
  • non-convex optimization

Fingerprint Dive into the research topics of 'Heterogeneous multireference alignment: A single pass approach'. Together they form a unique fingerprint.

  • Cite this

    Boumal, N., Bendory, T., Lederman, R. R., & Singer, A. (2018). Heterogeneous multireference alignment: A single pass approach. In 2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018 (pp. 1-6). (2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CISS.2018.8362313