Robust Synchronization and 3D Reconstruction from Cryo-EM Images

Abstract

Synchronization of rotations is the problem of estimating a set of rotations $R_1,R_2,ldots,R_n$ based on noisy measurements of relative rotations $R_{i}^{-1}R_{j}$. This fundamental problem has found a broad range of applications in computer vision, sensor network localization, structural biology, among others. A closely related problem is the "orientation assignment problem", which is to estimate the rotations $R_1,R_2,ldots,R_n$ of a three-dimensional (3D) object given a finite set of two-dimensional (2D) tomographic projection images $P_1,P_2,ldots,P_n$. The ``orientation assignment problem'' is particularly important in single-particle reconstruction from cryo-electron microscopy (cryo-EM) images, for determining 3D structures of molecules that cannot be crystallized for X-ray.

In this thesis, we propose and analyze new algorithms for the synchronization problem, and the problems on orientation determination and 3D inversion in cryo-EM reconstruction. In the first chapter, we overview the background of the synchronization problem and the problems in cryo-EM reconstruction. In chapter 2, we propose a Least Unsquared Deviations (LUD) method for the synchronization problem, and prove exact and stable recovery of this method for a specific probabilistic model of the measurements. We discover a phase transition behavior of LUD and present a theoretical justification. The LUD problem is solved by semidefinite relaxation (SDR) and the alternating direction method of multipliers (ADMM). In chapter 3, we apply LUD based algorithms to improve the accuracy of orientation determination from cryo-EM images. In chapter 4, we propose a fast and accurate Fourier-based iterative 3D inversion algorithm in cryo-EM, which exploits the Toeplitz structure of the composition of backward and forward projectors. We conclude this thesis in chapter 5 by summarizing our contributions and discussing directions for future work.