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

DOI10.1088/1361-6420/AB7D2CzbMATH Open1470.92163arXiv1505.03840OpenAlexW3010359926MaRDI QIDQ5000617FDOQ5000617

Afonso S. Bandeira, A. Singer, R. R. Lederman, Yutong Chen

Publication date: 14 July 2021

Published in: Inverse Problems (Search for Journal in Brave)

Abstract: Let $mathcalG$ be a compact group and let $f_{ij}in{L}^2(mathcalG)$. We define the Non-Unique Games (NUG) problem as finding $g_1,dots,g_{n}inmathcalG$ to minimize $su{m}_{i,j=1}^n{f}_{ij}left(g_i{g}_j^{-1}ight)$. We devise a relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of $f_{ij}$ over $mathcalG$, which can then be solved efficiently. 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 in cryo-Electron Microscopy.

Full work available at URL: https://arxiv.org/abs/1505.03840

Recommendations

• Tsirelson's problem and an embedding theorem for groups arising from non-local games
• Computational Science - ICCS 2004
• Application of the representations of symmetric groups to characterizing solutions of games in partition function form
• The complexity of the nucleolus in compact games
• A noncooperative game on polyhedral sets
• Impartial achievement games for generating generalized dihedral groups
• scientific article; zbMATH DE number 1778404
• Orbits of crystallographic embedding of non-crystallographic groups and applications to virology
• Orientation determination of cryo-EM images using least unsquared deviations
• Solving singular evolution problems in sub-Riemannian groups via deterministic games

zbMATH Keywords

optimizationpattern recognitioncomputer visioncryo-EM

Mathematics Subject Classification ID

Applications of game theory (91A80) Semidefinite programming (90C22) Biomedical imaging and signal processing (92C55) Harmonic analysis on specific compact groups (43A75)

Cites Work

• Title not available (Why is that?)
• Semidefinite Programming
• Exact Recovery in the Stochastic Block Model
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• The mathematics of computerized tomography
• Title not available (Why is that?)
• Semidefinite relaxation and nonconvex quadratic optimization
• Semidefinite Optimization and Convex Algebraic Geometry
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A survey on spherical designs and algebraic combinatorics on spheres
• Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming
• A Cheeger Inequality for the Graph Connection Laplacian
• Positive trigonometric polynomials and signal processing applications
• Viewing Angle Classification of Cryo-Electron Microscopy Images Using Eigenvectors
• Viewing Direction Estimation in Cryo-EM Using Synchronization
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Approximating the cut-norm via Grothendieck's inequality
• Efficient rounding for the noncommutative grothendieck inequality
• Angular synchronization by eigenvectors and semidefinite programming
• Title not available (Why is that?)
• FFTs on the rotation group
• Title not available (Why is that?)
• Random Laplacian matrices and convex relaxations
• Multireference alignment using semidefinite programming
• Near-optimal algorithms for unique games
• Semidefinite Descriptions of the Convex Hull of Rotation Matrices
• Representations of compact groups and spherical harmonics
• Synchronization overZ₂and community detection in signed multiplex networks with constraints
• A representation theory perspective on simultaneous alignment and classification

Cited In (17)

• Multi-Reference Alignment in High Dimensions: Sample Complexity and Phase Transition
• A max-cut approach to heterogeneity in cryo-electron microscopy
• Estimation under group actions: recovering orbits from invariants
• Orbit recovery for band-limited functions
• Power spectrum unbiasing for dilation-invariant multi-reference alignment
• Orientation estimation of cryo-EM images using projected gradient descent method
• An extension of the angular synchronization problem to the heterogeneous setting
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Optimal rates of estimation for multi-reference alignment
• Regularizing Orientation Estimation in Cryogenic Electron Microscopy Three-Dimensional Map Refinement through Measure-Based Lifting over Riemannian Manifolds
• Toward Single Particle Reconstruction without Particle Picking: Breaking the Detection Limit
• Cohomology of Cryo-Electron Microscopy
• Signal recovery from a few linear measurements of its high-order spectra
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Averaging orientations with molecular symmetry in cryo-EM
• A representation theory perspective on simultaneous alignment and classification
• Computed Origami Tomography

Uses Software

• ASPIRE

This page was built for publication: Non-unique games over compact groups and orientation estimation in cryo-EM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000617)