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

Computer Science/Discrete Mathematics Seminar I
Topic:Non-unique games over compact groups and orientation estimation in cryo-EM
Speaker:Amit Singer
Affiliation:Princeton University
Date:Monday, November 7
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2016/1107-AmitSinger

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