  Let $\mathcal{G}$ be a compact group and let $f_{ij} \in L^2(\mathcal{G})$.
We define the Non-Unique Games (NUG) problem as finding $g_1,\dots,g_n \in
\mathcal{G}$ to minimize $\sum_{i,j=1}^n f_{ij} \left( g_i g_j^{-1}\right)$. We
devise a relaxation of the NUG problem to a semidefinite program (SDP) by
taking the Fourier transform of $f_{ij}$ over $\mathcal{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.
