Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp013484zk77n
Title: Rigorous Ab-Initio Modeling in Microscopy: a fast, stable and provable algorithm to estimate 3D molecular structure from uniformly oriented 2D projection images
Authors: Liu, Changshuo
Advisors: Singer, Amit
Kileel, Joe
Boumal, Nicolas
Department: Mathematics
Certificate Program: Applications of Computing Program
Class Year: 2019
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.
URI: http://arks.princeton.edu/ark:/88435/dsp013484zk77n
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
This content is embargoed until 2021-07-01. For more information contact the Mudd Manuscript Library.


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.