{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:38:04Z","timestamp":1787323084991,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>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 \u201cangular reconstitution\u201d 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.<\/jats:p>","DOI":"10.1137\/090767777","type":"journal-article","created":{"date-parts":[[2011,6,7]],"date-time":"2011-06-07T18:19:40Z","timestamp":1307470780000},"page":"543-572","source":"Crossref","is-referenced-by-count":140,"title":["Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming"],"prefix":"10.1137","volume":"4","author":[{"given":"A.","family":"Singer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y.","family":"Shkolnisky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,6,7]]},"reference":[{"key":"R1","unstructured":"J. Frank,\n                      Three-Dimensional Electron Microscopy of Macromolecular Assemblies: Visualization of Biological Molecules in Their Native State\n                      , Oxford University Press, New York, 2006."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1152\/physiol.00045.2005"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1017\/S0033583504003920"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.str.2008.02.007"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0711623105"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.str.2004.12.016"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2818.1987.tb01333.x"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/j.1460-2075.1987.tb04865.x"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(90)90038-W"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF00140118"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3991(94)90038-8"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3991(87)90078-7"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1017\/S0033583500003644"},{"key":"R14","unstructured":"B. Vainshtein and A. Goncharov,\n                      Determination of the spatial orientation of arbitrarily arranged identical particles of an unknown structure from their projections\n                      , in Proceedings of the 11th International Congress on Electron Mircoscopy, 1986, pp. 459\u2013460."},{"key":"R15","first-page":"195","volume":"11","author":"Van Heel M.","year":"1997","journal-title":"Scanning Microscopy","ISSN":"https:\/\/id.crossref.org\/issn\/0891-7035","issn-type":"print"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.9.001749"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3991(96)00037-X"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"S. P. Mallick, S. Agarwal, D. J. Kriegman, S. J. Belongie, B. Carragher, and C. S. Potter,\n                      Structure and view estimation for tomographic reconstruction: A Bayesian approach\n                      , in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Volume II, 2006, pp. 2253\u20132260.","DOI":"10.1109\/CVPR.2006.295"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsb.2009.11.003"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2009.11.003"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"S. Basu and Y. Bresler,\n                      Uniqueness of tomography with unknown view angles,\n                      IEEE Trans. Image Process. 9 (2000), pp. 1094\u20131106.","DOI":"10.1109\/83.846251"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"S. Basu and Y. Bresler,\n                      Feasibility of tomography with unknown view angles,\n                      IEEE Trans. Image Process. 9 (2000), pp. 1107\u20131122.","DOI":"10.1109\/83.846252"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2008.2002305"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"F. Natterer,\n                      The Mathematics of Computerized Tomography\n                      , Classics Appl. Math. 32, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898719284"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1987.4767965"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.2307\/1970079"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.2307\/1970008"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/S1063-5203(03)00030-7"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/060650283"},{"key":"R33","first-page":"121","volume":"14","author":"Coifman R. R.","year":"1968","journal-title":"Enseignement Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0013-8584","issn-type":"print"},{"key":"R34","unstructured":"R. Hadani and A. Singer,\n                      Representation theoretic patterns in cryo electron microscopy\n                      I\n                      \u2014The intrinsic reconstitution algorithm\n                      , Ann. of Math., to appear."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785860"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/s002200050743"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02100489"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0466-z"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-007-0209-3"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2010.02.001"},{"key":"R42","unstructured":"T. M. Cover and J. A. Thomas,\n                      Elements of Information Theory\n                      , Wiley, New York, 1991."},{"key":"R43","unstructured":"R. G. Gallager,\n                      Information Theory and Reliable Communication\n                      , Wiley, New York, 1968."}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090767777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:41:14Z","timestamp":1787319674000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090767777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090767777"],"URL":"https:\/\/doi.org\/10.1137\/090767777","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}