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

13 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
Country/TerritoryUnited 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