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

2015/05/14 by Afonso S. Bandeira, Yutong Chen, Bandeira, Afonso S. +3 · 3 citations
Biochemistry, Genetics and Molecular Biology · Mathematics · Medicine · #Advanced Electron Microscopy Techniques and Applications #Computer Vision and Pattern Recognition (cs.CV) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Genetic factors in colorectal cancer #Mathematical Approximation and Integration #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1505.03840

openalex publication_date 2015/05/14 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

Let \G be a compact group and let f_ij \∈ L²(\G).\nWe define the Non-Unique Games (NUG) problem as finding g₁,\…,g_n \∈\n\G to minimize \∑_i,j=1ⁿ f_ij \( g_i g_j^-1\). We\ndevise a relaxation of the NUG problem to a semidefinite program (SDP) by\ntaking the Fourier transform of f_ij over \G, which can then be\nsolved efficiently. The NUG framework can be seen as a generalization of the\nlittle Grothendieck problem over the orthogonal group and the Unique Games\nproblem and includes many practically relevant problems, such as the maximum\nlikelihood estimator to registering bandlimited functions over the unit sphere\nin d-dimensions and orientation estimation in cryo-Electron Microscopy.\n

Cited by

• Misspecified Maximum Likelihood Estimation for Non-Uniform Group Orbit Recovery
• Functional Multi-Reference Alignment via Deconvolution
• Higher-Order Group Synchronization

Related

• A Representation Theory Perspective on Simultaneous Alignment and Classification
• Estimation under group actions: Recovering orbits from invariants
• Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
• Unique Games and Games Based on Groups
• Playing Unique Games on Certified Small-Set Expanders