Representation Theoretic Patterns in Three-Dimensional Cryo-Electron Microscopy II-The Class Averaging Problem

Vector Diffusion Maps and the Connection Laplacian

We introduce vector diffusion maps (VDM), a new mathematical framework for organizing and analyzing massive high-dimensional data sets, images, and shapes. VDM is a mathematical and algorithmic generalization of diffusion maps and other nonlinear dimensionality reduction methods, such as LLE, ISOMAP, and Laplacian eigenmaps. While existing methods are either directly or indirectly related to the heat kernel for functions over the data, VDM is based on the heat kernel for vector fields. VDM provides tools for organizing complex data sets, embedding them in a low-dimensional space, and interpolating and regressing vector fields over the data. In particular, it equips the data with a metric, which we refer to as the vector diffusion distance. In the manifold learning setup, where the data set is distributed on a low-dimensional manifold ℳ ^d embedded in ℝ ^p , we prove the relation between VDM and the connection Laplacian operator for vector fields over the manifold.

Representation theoretic patterns in three dimensional Cryo-Electron Microscopy I: The intrinsic reconstitution algorithm

In this paper, we reveal the formal algebraic structure underlying the intrinsic reconstitution algorithm, introduced by Singer and Shkolnisky in [9], for determining three dimensional macromolecular structures from images obtained by an electron microscope. Inspecting this algebraic structure, we obtain a conceptual explanation for the admissibility (correctness) of the algorithm and a proof of its numerical stability. In addition, we explain how the various numerical observations reported in that work follow from basic representation theoretic principles.

Viewing Angle Classification of Cryo-Electron Microscopy Images Using Eigenvectors

The cryo-electron microscopy (cryo-EM) reconstruction problem is to find the three-dimensional structure of a macromolecule given noisy versions of its two-dimensional projection images at unknown random directions. We introduce a new algorithm for identifying noisy cryo-EM images of nearby viewing angles. This identification is an important first step in three-dimensional structure determination of macromolecules from cryo-EM, because once identified, these images can be rotationally aligned and averaged to produce "class averages" of better quality. The main advantage of our algorithm is its extreme robustness to noise. The algorithm is also very efficient in terms of running time and memory requirements, because it is based on the computation of the top few eigenvectors of a specially designed sparse Hermitian matrix. These advantages are demonstrated in numerous numerical experiments.