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

arXiv: https://arxiv.org/abs/1505.03840 · HTML: https://mlsanity.com/paper/1505.03840/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2015.

## Built on by (most cited first, 8 of 8)

- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Ab-initio Contrast Estimation and Denoising of Cryo-EM Images](https://mlsanity.com/paper/2202.07737/) (2022)
- [An accelerated expectation-maximization algorithm for multi-reference alignment](https://mlsanity.com/paper/2105.07372/) (2021)
- [Unrolled algorithms for group synchronization](https://mlsanity.com/paper/2207.09418/) (2022)
- [Higher-Order Group Synchronization](https://mlsanity.com/paper/2505.21932/) (2025)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)
- [Multi-Irreducible Spectral Synchronization for Robust Rotation Averaging](https://mlsanity.com/paper/2311.16544/) (2023)
- [Orientation Estimation of Cryo-EM Images for Molecules with Arbitrary Symmetry by Semidefinite Programming](https://mlsanity.com/paper/2610.18691/) (2026)

## Abstract (arXiv)

Let G be a compact group and let fij ∈ L2(G). We define the Non-Unique Games (NUG) problem as finding g1,dots,gn ∈ G to minimize sumi,j=1n fij left( gi gj-1right). We devise a relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of fij over G, 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.