Non-unique games over compact groups and orientation estimation in cryo-EM

Afonso S. Bandeira, Yutong Chen, Roy R. Lederman, Amit Singer

Research output: Contribution to journalArticle

Abstract

Let G be a compact group and let fij ∈ C(G). We define the non-unique games (NUG) problem as finding g1, ⋯, gn ∈ G to minimize Pnij=1 fij (gig-1j). We introduce a convex relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of f ij over G. The NUG framework can be seen as a generalization of the little Grothendieck problem over the orthogonal group and the unique games problem and includes many practically relevant problems, such as the maximum likelihood estimator to registering bandlimited functions over the unit sphere in d-dimensions and orientation estimation of noisy cryo-electron microscopy (cryo-EM) projection images. We implement an SDP solver for the NUG cryo-EM problem using the alternating direction method of multipliers (ADMM). Numerical study with synthetic datasets indicate that while our ADMM solver is slower than existing methods, it can estimate the rotations more accurately, especially at low signal-to-noise ratio (SNR).

Original languageEnglish (US)
Article number064002
JournalInverse Problems
Volume36
Issue number6
DOIs
StatePublished - Jun 1 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Mathematical Physics
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • computer vision
  • cryo-EM
  • optimization
  • pattern recognition

Fingerprint Dive into the research topics of 'Non-unique games over compact groups and orientation estimation in cryo-EM'. Together they form a unique fingerprint.

  • Cite this