Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming

A. Singer, Y. Shkolnisky

Research output: Contribution to journalArticlepeer-review

126 Scopus citations


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 languageEnglish (US)
Pages (from-to)543-572
Number of pages30
JournalSIAM Journal on Imaging Sciences
Issue number2
StatePublished - 2011

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • General Mathematics


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


Dive into the research topics of 'Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming'. Together they form a unique fingerprint.

Cite this