Non-Unique Games Over Compact Groups and Applications

Abstract

Let G be a compact group and let fij 2 L2(G). We dene the Non-Unique Games

(NUG) problem as nding g1; : : : ; gn 2 G to minimize

Pn

i;j=1 fij

􀀀

gig􀀀1

j

. We devise

a relaxation of the NUG problem to a semidenite program (SDP) by taking

the Fourier transform of fij over G, which can then be solved eciently. The NUG

framework can be seen as a generalization of the Unique Games problem and the

little Grothendieck problem over the orthogonal group, 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.