Rigorous Ab-Initio Modeling in Microscopy: a fast, stable and provable algorithm to estimate 3D molecular structure from uniformly oriented 2D projection images

Abstract

Single particle reconstruction (SPR) using cryo-electron microscopy (cryo-EM) is a popular technique for determining the 3D structure of macro-molecular complexes from noisy 2D tomographic images taken at random viewing directions. Many mainstream algorithms start with an initial guess of the structure and iteratively refine this using the images. Such algorithms’ performance is often heavily dependent on the quality of the initial structure, necissitating an efficient algorithm to compute a good ab-initio estimate of the molecular structure. Recently, there has been a resurgence of effort to use Zvi Kam’s autocorrelation analysis to obtain such an estimate, under the assumption that the viewing directions of images are uniformly oriented. In Kam’s original paper from 1980, by estimating the second-order autocorrelation from images, the author shows that the expansion coefficients for the molecular structure are determined up to a sequence of missing orthogonal matrices. There have been attempts to recover these missing matrices from the third-order autocorrelation, but the computational process is often costly and lacks mathematical guarantees.

In this paper, we provide a mathematical proof that, under certain explicit genericity conditions on the expansion coefficients, the third-order moment of images uniquely determines these orthogonal matrices up to the rotation and reflection of the molecule. In addition, we present an efficient algorithm called Orthogonal Matrix Retrieval via Backward Peeling and Forward Marching that computes these orthogonal matrices, recovering the analytic solution exactly in the case of noiseless moments. To our knowledge, ours is the first ab-initio algorithm with such a provable guarantee. The method exploits special structure in Kam’s moments to solve an over-determined system of multivariate polynomials by a certain nontrivial sequence of linear algebra computations. Numerical experiments are performed on synthetically generated data, establishing stability in the noisy moments case and confirming the competitive speed of our method in practice.

The method exploits special structure in Kam’s moments to solve an over-determined system of multivariate polynomials by a certain nontrivial sequence of linear algebra computations. Numerical experiments are performed on synthetically generated data, establishing stability in the noisy moments case and confirming the competitive speed of our method in practice.