## Abstract

The cryo-electron microscopy reconstruction problem is to find the three-dimensional (3D) structure of a macromolecule given noisy samples of its two-dimensional projection images at unknown random directions. Present algorithms for finding an initial 3D structure model are based on the "angular reconstitution" method in which a coordinate system is established from three projections, and the orientation of the particle giving rise to each image is deduced from common lines among the images. However, a reliable detection of common lines is difficult due to the low signal-to-noise ratio of the images. In this paper we describe two algorithms for finding the unknown imaging directions of all projections by minimizing global self-consistency errors. In the first algorithm, the minimizer is obtained by computing the three largest eigenvectors of a specially designed symmetric matrix derived from the common lines, while the second algorithm is based on semidefinite programming (SDP). Compared with existing algorithms, the advantages of our algorithms are five-fold: First, they accurately estimate all orientations at very low common-line detection rates; second, they are extremely fast, as they involve only the computation of a few top eigenvectors or a sparse SDP; third, they are nonsequential and use the information in all common lines at once; fourth, they are amenable to a rigorous mathematical analysis using spectral analysis and random matrix theory; and finally, the algorithms are optimal in the sense that they reach the information theoretic Shannon bound up to a constant for an idealized probabilistic model.

Original language | English (US) |
---|---|

Pages (from-to) | 543-572 |

Number of pages | 30 |

Journal | SIAM Journal on Imaging Sciences |

Volume | 4 |

Issue number | 2 |

DOIs | |

State | Published - 2011 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)
- Applied Mathematics

## Keywords

- Angular reconstitution
- Cryo-electron microscopy
- Random matrices
- Rotation group SO(3)
- Semicircle law
- Semidefinite programming
- Tomography