NON-UNIQUE GAMES OVER COMPACT GROUPS AND ORIENTATION ESTIMATION IN CRYO-EM

Abstract

Let $𝒢$ be a compact group and let $f_{ij}\in C\left(𝒢\right)$ . We define the Non-Unique Games (NUG) problem as finding $g_1,\dots ,g_n\in 𝒢$ to minimize ${\sum }_{i,j=1}^n{f}_{ij}\left(g_i{g}_j^{-1}\right)$ . We introduce a convex relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of $f_{ij}$ over $𝒢$ . 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 of noisy cryo-Electron Microscopy (cryo-EM) projection images. We implement a SDP solver for the NUG cryo-EM problem using the alternating direction method of multipliers (ADMM). Numerical study with synthetic datasets indicate that while our ADMM solver is slower than existing methods, it can estimate the rotations more accurately, especially at low signal-to-noise ratio (SNR).

Keywords: Computer vision; Primary: 00A69; Secondary: 90C34, 20C40; algorithms; cryo-EM; optimization; pattern recognition.

Figure 1.1.

Illustration of the cryo-EM imaging process: A molecule is imaged after being frozen at a random (unknown) rotation and a tomographic 2-dimensional projection is captured. Given a number of tomographic projections taken at unknown rotations, we are interested in determining such rotations with the objective of reconstructing the molecule density. Images courtesy of Amit Singer and Yoel Shkolnisky [42].

Figure 2.1.

Illustration of the registration problem in $S^1$. The first column consists of a noiseless signal at three different shifts, the second column represents an instance for which the template $x$ is known and matched filtering is effective to estimate the shifts. However, in the examples we are interested in the template is unknown (last two columns) rendering the problem of estimating the shifts significantly harder.

Figure 2.2.

An illustration of registration in 2-dimensions. The left four spheres provide examples of clean signals $y_i$ and the right four spheres are of noisy observations. Note that the images are generated using a quantization of the sphere.

Figure 2.3.

Sample images from the E. coli 50S ribosomal subunit, generously provided by Dr. Fred Sigworth at the Yale Medical School.

Figure 2.4.

An illustration of the use of the Fourier slice theorem and the common lines approach to the orientation estimation problem in cryo-EM. Image courtesy of Amit Singer and Yoel Shkolnisky [42].

Figure 6.1.

Three cryo-EM images uniquely determine their orientations up to handedness. Image courtesy of Singer et al. [41].

Figure 6.2.

Example created by Jiang and Chiu available at http://jiang.bio.purdue.edu/software/ctf/ctfapplet.html

Figure 6.3.

Distribution of contrast in the experimental dataset EMPIAR-10028.