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

DOI10.1088/1361-6420/AB7D2CMaRDI QIDQ5000617zbMATH OpenOpenAlexFDO

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

Publication date 14 July 2021

Published in Inverse Problems (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3140172 (Why is no real title available?)
• scientific article; zbMATH DE number 3467457 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5937160 (Why is no real title available?)
• A Cheeger Inequality for the Graph Connection Laplacian
• A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
• A representation theory perspective on simultaneous alignment and classification
• A survey on spherical designs and algebraic combinatorics on spheres
• Angular synchronization by eigenvectors and semidefinite programming
• Approximating the cut-norm via Grothendieck's inequality
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Efficient rounding for the noncommutative Grothendieck inequality
• Exact Recovery in the Stochastic Block Model
• FFTs on the rotation group
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Multireference alignment using semidefinite programming
• Near-optimal algorithms for unique games
• On the power of unique 2-prover 1-round games
• Positive trigonometric polynomials and signal processing applications
• Random Laplacian matrices and convex relaxations
• Representations of compact groups and spherical harmonics
• Semidefinite Descriptions of the Convex Hull of Rotation Matrices
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite Programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Synchronization overZ₂and community detection in signed multiplex networks with constraints
• The mathematics of computerized tomography
• Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
• Viewing angle classification of cryo-electron microscopy images using eigenvectors
• Viewing direction estimation in cryo-EM using synchronization

Cited in

(17)

• Cohomology of cryo-electron microscopy
• A max-cut approach to heterogeneity in cryo-electron microscopy
• Estimation under group actions: recovering orbits from invariants
• Orbit recovery for band-limited functions
• Computed origami tomography
• Power spectrum unbiasing for dilation-invariant multi-reference alignment
• Orientation estimation of cryo-EM images using projected gradient descent method
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• An extension of the angular synchronization problem to the heterogeneous setting
• Optimal rates of estimation for multi-reference alignment
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• 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
• 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

Describes a project that uses

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)