OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 20, Iss. 12 — Jun. 4, 2012
  • pp: 12799–12826
« Show journal navigation

The symmetries of image formation by scattering. I. Theoretical framework

Dimitrios Giannakis, Peter Schwander, and Abbas Ourmazd  »View Author Affiliations


Optics Express, Vol. 20, Issue 12, pp. 12799-12826 (2012)
http://dx.doi.org/10.1364/OE.20.012799


View Full Text Article

Acrobat PDF (1190 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We perceive the world through images formed by scattering. The ability to interpret scattering data mathematically has opened to our scrutiny the constituents of matter, the building blocks of life, and the remotest corners of the universe. Here, we present an approach to image formation based on the symmetry properties of operations in three-dimensional space. Augmented with graph-theoretic means, this approach can recover the three-dimensional structure of objects from random snapshots of unknown orientation at four orders of magnitude higher complexity than previously demonstrated. This is critical for the burgeoning field of structure recovery by X-ray Free Electron Lasers, as well as the more established electron microscopic techniques, including cryo-electron microscopy of biological systems. In a subsequent paper, we demonstrate the recovery of structure and dynamics from experimental, ultralow-signal random sightings of systems with X-rays, electrons, and photons, with no orientational or timing information.

© 2012 OSA

1. Introduction

We perceive by constructing three-dimensional (3D) models from random sightings of objects in different orientations. Our ability to recognize that we are seeing a profile even when the face is unknown [1

1. W. A. Freiwald and D. Y. Tsao“Functional compartmentalization and viewpoint generalization within the macaque face-processing system,” Science 330, 845–851 (2010). [CrossRef] [PubMed]

] suggests that perception may rely on object-independent properties of the image formation process. The discovery of these properties would underpin our mathematical formalisms, enhance our computational reach, and allow us to recover the structure and perhaps dynamics of complex systems such as macromolecules.

Here, we show that image formation by scattering possesses specific symmetries, which stem from the nature of operations in three-dimensional (3D) space. This follows from a theoretical framework, which considers the information contained in a collection of random sightings of an object. An example is a collection of two-dimensional (2D) snapshots of a moving head, or a rotating molecule. We show that the information gleaned from random sightings of an object by scattering onto a 2D detector can be represented as a Riemannian manifold with properties resembling well-known systems in general relativity and quantum mechanics. As demonstrated below and in a subsequent paper, this allows one to efficiently construct models of an object and its dynamics from random, ultralow-signal snapshots, as obtained, e.g., from single biological molecules by X-ray Free Electron Lasers [2

2. M. Seibert, T. Ekeberg, F. R. N. C. Maia, M. Svenda, J. Andreasson, O. Jönsson, D. Odić, B. Iwan, A. Rocker, D. Westphal, M. Hantke, D. P. DePonte, A. Barty, J. Schulz, L. Gumprecht, N. Coppola, A. Aquila, M. Liang, T. A. White, A. Martin, C. Caleman, S. Stern, C. Abergel, V. Seltzer, J. Claverie, C. Bostedt, J. D. Bozek, S. Boutet, A. A. Miahnahri, M. Messerschmidt, J. Krzywinski, G. Williams, K. O. Hodgson, M. J. Bogan, C. Y. Hampton, R. G. Sierra, D. Starodub, I. Andersson, S. Bajt, M. Barthelmess, J. C. H. Spence, P. Fromme, U. Weierstall, R. Kirian, M. Hunter, R. B. Doak, S. Marchesini, S. P. Hau-Riege, M. Frank, R. L. Shoeman, L. Lomb, S. W. Epp, R. Hartmann, D. Rolles, A. Rudenko, C. Schmidt, L. Foucar, N. Kimmel, P. Holl, B. Rudek, B. Erk, A. Hömke, C. Reich, D. Pietschner, G. Weidenspointner, L. Strüder, G. Hauser, H. Gorke, J. Ullrich, I. Schlichting, S. Herrmann, G. Schaller, F. Schopper, H. Soltau, K. Kühnel, R. Andritschke, C. Schröter, F. Krasniqi, M. Bott, S. Schorb, D. Rupp, M. Adolph, T. Gorkhover, H. Hirsemann, G. Potdevin, H. Graafsma, B. Nilsson, H. N. Chapman, and J. Hajdu“Single mimivirus particles intercepted and imaged with an X-ray laser,” Nature 470, 78–81 (2011). [CrossRef] [PubMed]

] and cryo-electron microscopy [3

3. J. Frank“Single-particle imaging of macromolecules by cryo-electron microscopy,” Annu. Rev. Biophys. Biomolec. Struct. 31, 303–319 (2002). [CrossRef]

, 4

4. N. Fischer, A. L. Konevega, W. Wintermeyer, M. V. Rodnina, and H. Stark“Ribosome dynamics and tRNA movement by time-resolved electron cryomicroscopy,” Nature 466, 329–333 (2010). [CrossRef] [PubMed]

].

More generally, it is now well-established that numerical data clouds give rise to manifolds, whose properties can be accessed by powerful graph-theoretic methods [5

5. J. B. Tenenbaum, V. de Silva, and J. C. Langford“A global geometric framework for nonlinear dimensionality reduction,” Science 290, 2319–2323 (2000). [CrossRef] [PubMed]

10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

]. However, it has proved difficult to assign physical meaning to the results [11

11. R. R. Coifman, Y. Shkolnisky, F. J. Sigworth, and A. Singer“Reference free structure determination through eigenvectors of center of mass operators,” Appl. Comput. Harmon. Anal. 28, 296–312 (2010). [CrossRef] [PubMed]

, 12

12. A. L. Ferguson, A. Z. Panagiotopoulos, P. G. Debenedetti, and I. G. Kevrekidis“Systematic determination of order parameters for chain dynamics using diffusion maps,” Proc. Natl. Acad. Sci. U.S.A. 107, 13597–13602 (2010). [CrossRef] [PubMed]

]. Using tools developed in differential geometry, general relativity, and quantum mechanics, we elucidate the physical meaning of the outcome of graph-theoretic analysis of scattering data, without the need for restrictive a priori assumptions [13

13. A. Singer, R. R. Coifman, F. J. Sigworth, D. W. Chester, and Y. Shkolnisky“Detecting consistent common lines in cryo-EM by voting,” J. Struct. Biol. 169, 312–322 (2010). [CrossRef]

]. Finally, perception can be formulated as learning some functions on the observation manifold. Our approach is then tantamount to machine learning with a dictionary acquired from the empirically accessible eigenfunctions of well-known operators.

2. Conceptual outline

We are concerned with constructing a model from sightings of a system viewed in some projection, i.e., by accessing a subset of the variables describing the state of the system. A 3D model of an object, for example, can be constructed from an ensemble of 2D snapshots. Each snapshot can be represented by a vector with the pixel intensities as components. A collection of snapshots then forms a cloud of points in some high-dimensional data space (Fig. 1). In fact, the cloud defines a hypersurface (manifold) embedded in that space, with its dimensionality determined by the number of degrees of freedom available to the system. Snapshots from a rotating molecule, for example, form a 3D hypersurface.

Fig. 1 Intensity values of a snapshot on a detector with n pixels, represented as an n-dimensional vector. Changes in the object or its position alter the snapshot, causing the vector to trace out a manifold in the n-dimensional data space. The dimensionality of manifold is determined by the number of degrees of freedom available to the object. For instance, the rotations of a rigid object give rise to a 3D manifold.

3. Previous work

When the snapshots emanate from known object orientations and the signal is adequate, powerful tomographic approaches [19

19. F. NattererThe Mathematics of Computerized Tomography (SIAM, 2001). [CrossRef]

21

21. A. Sentenac, O. Haeberle, and K. Belkebir“Introduction,” J. Mod. Opt. 57, 685 (2010). [CrossRef]

] can be employed. 3D models can also be constructed when the snapshot orientations are unknown and the signal is low [3

3. J. Frank“Single-particle imaging of macromolecules by cryo-electron microscopy,” Annu. Rev. Biophys. Biomolec. Struct. 31, 303–319 (2002). [CrossRef]

] [signal-to-noise ratio (SNR) ∼ −5 dB], or extremely low [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

24

24. P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys. 12, 1–15 (2010). [CrossRef]

] (∼ 10−2 scattered photons per Shannon pixel with Poisson noise and background scattering). Finally, efforts are underway to recover structure, map conformations, and determine dynamics (“3D movies”) from random sightings of identical objects [2

2. M. Seibert, T. Ekeberg, F. R. N. C. Maia, M. Svenda, J. Andreasson, O. Jönsson, D. Odić, B. Iwan, A. Rocker, D. Westphal, M. Hantke, D. P. DePonte, A. Barty, J. Schulz, L. Gumprecht, N. Coppola, A. Aquila, M. Liang, T. A. White, A. Martin, C. Caleman, S. Stern, C. Abergel, V. Seltzer, J. Claverie, C. Bostedt, J. D. Bozek, S. Boutet, A. A. Miahnahri, M. Messerschmidt, J. Krzywinski, G. Williams, K. O. Hodgson, M. J. Bogan, C. Y. Hampton, R. G. Sierra, D. Starodub, I. Andersson, S. Bajt, M. Barthelmess, J. C. H. Spence, P. Fromme, U. Weierstall, R. Kirian, M. Hunter, R. B. Doak, S. Marchesini, S. P. Hau-Riege, M. Frank, R. L. Shoeman, L. Lomb, S. W. Epp, R. Hartmann, D. Rolles, A. Rudenko, C. Schmidt, L. Foucar, N. Kimmel, P. Holl, B. Rudek, B. Erk, A. Hömke, C. Reich, D. Pietschner, G. Weidenspointner, L. Strüder, G. Hauser, H. Gorke, J. Ullrich, I. Schlichting, S. Herrmann, G. Schaller, F. Schopper, H. Soltau, K. Kühnel, R. Andritschke, C. Schröter, F. Krasniqi, M. Bott, S. Schorb, D. Rupp, M. Adolph, T. Gorkhover, H. Hirsemann, G. Potdevin, H. Graafsma, B. Nilsson, H. N. Chapman, and J. Hajdu“Single mimivirus particles intercepted and imaged with an X-ray laser,” Nature 470, 78–81 (2011). [CrossRef] [PubMed]

], or non-identical members of heterogeneous ensembles [4

4. N. Fischer, A. L. Konevega, W. Wintermeyer, M. V. Rodnina, and H. Stark“Ribosome dynamics and tRNA movement by time-resolved electron cryomicroscopy,” Nature 466, 329–333 (2010). [CrossRef] [PubMed]

, 24

24. P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys. 12, 1–15 (2010). [CrossRef]

, 25

25. S. H. W. Scheres, H. Gao, M. Valle, G. T. Herman, P. P. B. Eggermont, J. Frank, and J.-M. Carazo“Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization,” Nat. Methods 4, 27–29 (2007). [CrossRef]

] and/or evolving systems [4

4. N. Fischer, A. L. Konevega, W. Wintermeyer, M. V. Rodnina, and H. Stark“Ribosome dynamics and tRNA movement by time-resolved electron cryomicroscopy,” Nature 466, 329–333 (2010). [CrossRef] [PubMed]

, 24

24. P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys. 12, 1–15 (2010). [CrossRef]

].

Data-analytical approaches now include powerful graph-theoretic and/or differential geometric means to deduce information from the global structure of the data representing the (nonlinear) correlations in the dataset [5

5. J. B. Tenenbaum, V. de Silva, and J. C. Langford“A global geometric framework for nonlinear dimensionality reduction,” Science 290, 2319–2323 (2000). [CrossRef] [PubMed]

10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

, 26

26. L. Younes, P. W. Michor, J. Shah, and D. Mumford“A metric on shape space with explicit geodesics,” Atti Accad. Naz. Lincei, Cl. Sci. Fis., Mat. Nat., Rend. Lincei, Mat. Appl. 9, 25–57 (2008). [CrossRef]

, 27

27. T. Lin, H. Zha, and S. Lee“Riemannian manifold learning fo rnonlinear dimensionality reduction,” in ECCV Part I, LNCS,, A. Leondardis, H. Bischof, and A. Pinzeds. (Springer-Verlag, 2006), 44–55.

]. Ideally, this structure takes the form of a low-dimensional manifold in some high-dimensional space dictated by the measurement apparatus (see Fig. 1). These so-called manifold-embedding approaches are in essence nonlinear (kernel) principal components techniques [28

28. B. Schölkopf, B. Smola, and K.-R. Müller“Nonlinear component analysis as an kernel eigenvalue problem,” Neural Comput. 10, 1299–1319 (1998). [CrossRef]

], which seek to display in some low-dimensional Euclidean space the manifold representing the correlations in the data. While powerful, such approaches face three challenges: computational cost; robustness against noise; and the assignment of physical meaning to the outcome of the analysis, i.e., physically correct interpretation.

Bayesian manifold approaches [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

, 29

29. C. M. Bishop, M. Svensen, and C. K. I. Williams“GTM: The generative topographic mapping,” Neural Comput. 463, 379–383 (1998).

] and their equivalents [23

23. N. T. D. Loh and V. Elser“Reconstruction algorithm for single-particle diffraction imaging experiments,” Phys. Rev. E 80, 026705–1–026705–20 (2009). [CrossRef]

, 30

30. B. Moths and A. Ourmazd“Bayesian algorithms for recovering structure from single-particle diffraction snapshots of unknown orientation: a comparison,” Acta Crystallogr. A67 (2011).

] are able to operate at extremely low signal, but require prior knowledge of the manifold dimensionality and its physical meaning. They also display extremely unfavorable scaling behaviors [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

24

24. P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys. 12, 1–15 (2010). [CrossRef]

, 30

30. B. Moths and A. Ourmazd“Bayesian algorithms for recovering structure from single-particle diffraction snapshots of unknown orientation: a comparison,” Acta Crystallogr. A67 (2011).

]. It has thus not been possible, for example, to reconstruct objects with diameters exceeding eight times the spatial resolution, severely limiting the size of amenable objects and/or the resolution of the reconstruction.

Non-Bayesian graph-theoretic methods are computationally efficient, but tend not to be robust against noise [31

31. M. Balasubramanian and E. L. Schwartz“The Isomap algorithm and topological stability,” Science 295, 5552 (2002). [CrossRef]

,32

32. R. Coifman, Y. Shkolnisky, F. Sigworth, and A. Singer“Graph Laplacian tomography from unknown random projections,” IEEE Trans. Image Process. 17, 1891–1899 (2008). [CrossRef] [PubMed]

]. More fundamentally, it has proved difficult to assign physical meaning to the outcome of graph-theoretic analyses [11

11. R. R. Coifman, Y. Shkolnisky, F. J. Sigworth, and A. Singer“Reference free structure determination through eigenvectors of center of mass operators,” Appl. Comput. Harmon. Anal. 28, 296–312 (2010). [CrossRef] [PubMed]

], in the sense that the meaning of the space in which the data manifold is embedded is unknown. Strategies to overcome this problem have included exploring the graph-theoretic consequences of specific changes in model systems [12

12. A. L. Ferguson, A. Z. Panagiotopoulos, P. G. Debenedetti, and I. G. Kevrekidis“Systematic determination of order parameters for chain dynamics using diffusion maps,” Proc. Natl. Acad. Sci. U.S.A. 107, 13597–13602 (2010). [CrossRef] [PubMed]

], making restrictive assumptions about the nature of the data, and/or extracting specific information from the data first and subjecting this information to graph-theoretic analysis [11

11. R. R. Coifman, Y. Shkolnisky, F. J. Sigworth, and A. Singer“Reference free structure determination through eigenvectors of center of mass operators,” Appl. Comput. Harmon. Anal. 28, 296–312 (2010). [CrossRef] [PubMed]

, 13

13. A. Singer, R. R. Coifman, F. J. Sigworth, D. W. Chester, and Y. Shkolnisky“Detecting consistent common lines in cryo-EM by voting,” J. Struct. Biol. 169, 312–322 (2010). [CrossRef]

].

In this paper, we present a computationally efficient theoretical framework capable of interpreting the outcome of graph-theoretic analysis of scattering data without restrictive assumptions. Using this approach, we demonstrate 3D structure recovery from 2D diffraction snapshots of unknown orientation at computational complexities four orders of magnitude higher than hitherto possible [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

, 23

23. N. T. D. Loh and V. Elser“Reconstruction algorithm for single-particle diffraction imaging experiments,” Phys. Rev. E 80, 026705–1–026705–20 (2009). [CrossRef]

]. In Paper II, we show that this framework can be used to: (1) recover structure from simulated and experimental snapshots at signal levels ∼ 10× lower than currently in use; and (2) reconstruct time-series (movies) from ultralow-signal random sightings of evolving objects. In sum, therefore, our approach offers a powerful route to recovering structure and dynamics (3D movies) from ultralow-signal snapshots with no orientational or timing information.

4. Symmetry-based analysis of scattering data

In this section we develop a mathematical framework for analyzing ensembles of 2D snapshots, using far-field scattering by a single object as a model problem to focus the discussion (see Sec. 4.1). (For a less mathematical description, see Paper II, section 3.) The basic principle of our approach, laid out in Sec. 4.2, is that the data acquisition process can be described as a manifold embedding Φ [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

, 34

34. S. LangIntroduction to Differentiable Manifolds (Springer-Verlag, 2002).

], mapping the set of orientations of the object, SO(3), to the (Hilbert) space of snapshots on the detector plane. As a result, the differential-geometric properties of the rotation group formally carry over to the scattering dataset. In particular, the dataset can be equipped with a homogeneous Riemannian metric B, whose Laplacian eigenfunctions are the well-known Wigner D-functions [35

35. E. P. WignerGroup Theory and its Application to the Quantum Mechanics of Atomic Spectra (Academic Press, 1959).

37

37. G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]

]. Here, a metric is called homogeneous if any two points on the data manifold can be connected via a transformation that leaves the metric invariant. We refer to this class of transformations as symmetries. In Sec. 4.3, we show that taking advantage of symmetry, as manifested in the properties of homogeneous metrics on SO(3) [38

38. B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D 8, 1048–1060 (1973). [CrossRef]

], leads to a powerful means for recovering snapshot orientations and hence the 3D structure of objects.

A number of sparse algorithms [7

7. M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput. 13, 1373–1396 (2003). [CrossRef]

,10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

] are able to compute discrete approximations of Laplacian eigenfunctions directly from the data. However, these algorithms do not provide the eigenfunctions associated with B, but rather the eigenfunctions of an induced metric g associated with the embedding Φ (i.e., the measurement process). The properties of this induced metric are discussed in Sec. 4.4. There, we show that g is not homogeneous, but admits a decomposition into a homogeneous metric plus a residual. The homogeneous part of g corresponds to a well-known solution of general relativity (the so-called Taub solution [39

39. A. H. Taub“Empty space-times admitting a three parameter group of motions,” Ann. Math. 53, 472–490 (1951). [CrossRef]

]), which has the important property of preserving the Wigner D-functions as solutions of the Laplacian eigenvalue problem [38

38. B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D 8, 1048–1060 (1973). [CrossRef]

]. As described in Sec. 4.5 (and demonstrated in Sec. 5 and Paper II), this property applies to a broad range of scattering modalities, and can be exploited to perform highly accurate 3D reconstruction in a computationally-efficient manner.

4.1. Image formation

We first treat image formation as elastic, kinematic scattering of unpolarized radiation onto a far-field detector in reciprocal space [40

40. J. M. CowleyDiffraction Physics, 3rd ed. (North Holland, 1995).

], where each incident photon can scatter from the object at most once (kinematic scattering), and energy is conserved (elastic scattering). We show later that our conclusions are more generally applicable. In this minimal model, illustrated in Fig. 2, an incident beam of radiation with wavevector q1 = Qz (we set Q > 0 by convention) is scattered by an object of density ρ(u) with Patterson function P(u) = ∫ duρ(u′)ρ(uu′) = P(−u), where u and u′ are position vectors in ℝ3. The structure-factor amplitude at point r⃗ on a detector plane fixed at right angles to the incident beam is given by the usual integral,
a(r)=[ω(r)duP(u)exp(iuq(r))]1/2,
(1)
where ω(r⃗) is an obliquity factor proportional to the solid angle subtended at u = 0 by the detector element at r⃗, and q(r⃗) is the change in wavevector due to scattering. In elastic scattering we have
q(r)=q2(r)q1,q2(r)=Q(sinθcosϕ,sinθsinϕ,cosϕ),
(2)
where q2(r⃗) is the scattered wavevector, and θ and ϕ are the polar and azimuthal angles in reciprocal space corresponding to position r⃗ on the detector plane (see Fig. 2). Note that, by the convolution theorem, the Fourier transform (P) of the Patterson function is equal to the non-negative function |(ρ)|2. As a result, no modulus sign is needed in Eq. (1), and a2(r⃗j) is equal to the intensity Ij at pixel j in Fig. 1.

Fig. 2 Geometry of image formation by scattering. q1 and q2 represent the wavevectors for the incident and scattered radiation, respectively, (x,y,z) the lab frame, and (r,ϕ) coordinates in the detector plane.

In an idealized, noise-free experiment involving a single object conformation, one observes a sequence of s snapshots on a detector of infinite extent, with the snapshots arising from random orientations of the object. Each snapshot is obtained from Eq. (1) by replacing P(u) with PR(u) = P(R−1u), where R is a 3 × 3 right-handed rotation matrix; i.e., RTR = I and det(R) = 1.

The set of all matrices satisfying these conditions form the 3D rotation group, SO(3). It is well known that SO(3) is a Lie group, i.e., it is a differentiable manifold (in this case of dimension 3) [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

,37

37. G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]

,41

41. A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).

]. Among the several parameterizations (coordinate charts) of SO(3), of interest to us here will be Euler angles, unit quaternions, and hyperspherical coordinates [42

42. J. B. KuipersQuaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality (Princeton University Press, 2002). [PubMed]

]. The last coordinate system stems from the fact that SO(3) has the topology of a three-sphere with its antipodal points identified.

For the remainder of this section, SO(3) will play the role of the latent manifold 𝒮, i.e., the set of degrees of freedom available to the object. In more general applications, the latent manifold would be augmented to contain the additional degrees of freedom, provided, of course, that these degrees of freedom admit a manifold description—a natural requirement for operations such as shifts and smooth conformational changes.

4.2. Riemannian formulation of image formation

We are concerned with intensity patterns generated by scattering, i.e., a subset of all possible patterns on a planar detector, referred to as data space. It is reasonable to expect that in a physical experiment involving a finite-power beam, the resulting distributions of structure-factor moduli belong to the set of square-integrable functions on the detector plane, L2(ℝ2). This is a Hilbert space of scalar functions fi equipped with the usual inner product
(f1,f2)=drf1(r)f2(r),
(3)
and corresponding norm
fi=(fi,fi)1/2.
(4)
In many respects, L2(ℝ2) can be though of as a generalization of Euclidean space to infinite dimensions. In particular, the L2 norm induces a distance ‖f1f2‖ analogous to the standard distance in finite-dimensional Euclidean space. Moreover, viewed as a manifold [43

43. S. LangFundamentals of Differential Geometry (Springer-Verlag, 1998).

], L2(ℝ2) has the important property that its elements are in one-to-one correspondence with its tangent spaces. Thus, the inner product in Eq. (3) can be interpreted as a metric tensor acting on pairs of tangent vectors on L2(ℝ2), or manifolds embedded in L2(ℝ2).

We describe the image formation process as an embedding [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

,34

34. S. LangIntroduction to Differentiable Manifolds (Springer-Verlag, 2002).

], Φ: 𝒮L2(ℝ2), taking the latent manifold into data space. For instance, in the present application with 𝒮 = SO(3), we have the explicit formula Φ(R) = aR, where R is an SO(3) rotation matrix and aR is the pattern on the detector given by Eq. (1) with P(u) replaced by P(R−1u).

The image = Φ(𝒮) of the latent manifold in data space is called the data manifold (see Fig. 1). In the absence of degeneracies such as object symmetry, the data and latent manifolds are diffeomorphic manifolds, i.e., completely equivalent from the point of view of differential geometry. In contrast with manifolds of shapes [26

26. L. Younes, P. W. Michor, J. Shah, and D. Mumford“A metric on shape space with explicit geodesics,” Atti Accad. Naz. Lincei, Cl. Sci. Fis., Mat. Nat., Rend. Lincei, Mat. Appl. 9, 25–57 (2008). [CrossRef]

, 44

44. A. M. Bronstein, M. M. Bronstein, and R. KimmelNumerical Geometry of Non-Rigid Shapes (Springer, 2007).

] which can contain singularities, these are manifolds of operations and thus generally well-behaved. The image of the latent manifold in data space is then a smooth (here, three-dimensional) embedded hypersurface, which preserves the topology of the latent manifold, and the structure of its tangent spaces [45

45. T. Sauer, J. A. Yorke, and M. Casdagli“Embedology,” J. Stat. Phys. 65, 579–616 (1991). [CrossRef]

]. Perception, at least in this simple model, can be viewed as understanding the map between the latent manifold of orientations and the data manifold of pixel intensities.

The inner product induced on the data manifold by the inner product in data space leads to a metric tensor g on the latent manifold, which encodes the properties of the object and the imaging process. This metric is constructed by converting the inner product of L2(ℝ2) in Eq. (3) to an equivalent inner product between tangent vectors on the data manifold. Specifically, given tangent vectors v1 and v2 on 𝒮, the induced metric g is defined through the action
g(v1,v2)=(Φ*(v1),Φ*(v2)),
(5)
where Φ* is the so-called derivative map associated with Φ [43

43. S. LangFundamentals of Differential Geometry (Springer-Verlag, 1998).

, 46

46. R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).

], carrying along tangent vectors on 𝒮 to tangent vectors on . The induced metric can be expanded in a suitable tensorial basis for 𝒮 as a 3 × 3 symmetric positive-definite (SPD) matrix with components gμν, viz.,
g=μ,ν=13gμνEμEν,
(6)
where {E1, E2, E3} is a basis of dual vector fields on 𝒮. Note that ds2 = g(δv, δv) corresponds to the squared distance between two nearby points on 𝒮 with relative separation δv. The integral of ds2 over curves on 𝒮 provides the data manifold with a notion of length and distance.

For the purposes of the symmetry analysis ahead, it is useful to consider expansions of g in a basis of right-invariant vector fields [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

, 41

41. A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).

], where, following the derivation in Appendix A, the components of g at orientation R are found to be
gμν(R)=drω(r)[JμqaR(q)][JνqaR(q)]|q(r).
(7)
In the above, ∫ dr⃗ denotes integration over the detector plane; q(r⃗) is the change in wavevector given by Eq. (2); = (/∂qx, /∂qy, /∂qz) is the gradient operator in reciprocal space; and Jμ are the 3 × 3 antisymmetric matrices in Eq. (36) generating rotations about the x, y, and z axes, respectively. As stated above, aR is the structure-factor amplitude corresponding to orientation R.

4.3. Symmetries

We now show that the Riemannian formulation outlined above reveals important symmetries, which can be used to determine the object orientation separately from the object itself. A fundamental concept in the discussion below is the notion of an isometry [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

, 46

46. R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).

]. Broadly speaking, an isometry is a continuous invertible transformation that leaves g invariant. More specifically, any diffeomorphism ϕ : 𝒮𝒮 mapping the latent manifold to itself induces a transformation ϕ* acting on tensors of the manifold; the latter will be an isometry if ϕ*(g) = g holds everywhere on 𝒮. A symmetry, therefore, in this context is an operation that leaves distances on the data manifold unchanged.

If the group of isometries of g acts transitively on 𝒮 (i.e., any two points in 𝒮 can be connected via a ϕ transformation), the pair (𝒮,g) becomes a Riemannian homogeneous space [41

41. A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).

]. We refer to any g meeting this condition as a homogeneous metric. Riemannian homogeneous spaces possess natural sets of orthonormal basis functions, analogous to the Fourier functions on the line and the spherical harmonics on the sphere, which can be employed for efficient data analysis [37

37. G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]

]. It is therefore reasonable to design algorithms that explicitly take into account the underlying Riemannian symmetries of scattering data sets.

The canonical classes of symmetry operations in problems involving orientational degrees of freedom are the so-called left and right multiplication maps [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

, 41

41. A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).

, 46

46. R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).

]. These maps, respectively denoted LQ and RQ, are parameterized by an arbitrary rotation matrix Q in SO(3), and act on SO(3) elements by multiplication from the left or the right, respectively. That is,
LQ(R)=QR,RQ(R)=RQ.
(8)
Viewed as groups, the collection of all left multiplication maps or right multiplication maps are isomorphic to SO(3), from which it immediately follows that their action is transitive. Thus, any metric g invariant under LQ or RQ (or both) makes (𝒮, g) a Riemannian homogeneous space.

The natural metric for the SO(3) latent manifold of orientations with these symmetries is the metric tensor B associated with the Killing form of the Lie algebra of SO(3) [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

, 41

41. A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).

]. This metric is bi-invariant under left and right translations. The corresponding group of isometries has SO(3) × SO(3) structure, i.e., it is a six-dimensional group. In hyperspherical coordinates (χ, θ, ϕ), B is represented by the diagonal matrix
[Bμν]=diag(1,sin2χ,sin2χsin2θ),
(9)
which is identical to the canonical metric on the three-sphere S3. For this reason B is frequently referred to as the “round” metric on SO(3).

A key implication of the symmetries of B pertains to the eigenfunctions of the corresponding Laplace-Beltrami operator ΔB [47

47. P. H. BérardSpectral Geometry: Direct and Inverse Problems, (Springer-Verlag, 1989).

, 48

48. S. RosenbergThe Laplacian on a Riemannian Manifold (Cambridge University Press, 1997). [CrossRef]

], defined as
ΔB(f)=|B|1/2μ,ν=1mμ(|B|1/2Bμννf)
(10)
for |B| = det[Bμν], [Bμν] = [Bμν]−1, and a scalar function f on SO(3). It is a well-known result in harmonic analysis that the eigenfunctions of ΔB are the Wigner D-functions [37

37. G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]

, 49

49. N. J. VilenkinSpecial Functions and the Theory of Group Representations, (American Mathematical Society, 1968).

, 50

50. D. A. Varshalovich, A. N. Moskalev, and V. K. KhersonskiiQuantum Theory of Angular Momentum (World Scientific, 1988).

], complex-valued functions on SO(3), which solve the eigenvalue problem
ΔBDmmj(R)=j(j+1)Dmmj(R)
(11)
with positive integer j and integers m and m′ in the range [−j, j]. Written out in terms of Euler angles in the zyz convention, (α1, α2, α3), explicit formulas for the j = 1 D-functions are
D001(α1,α2,α3)=cosα2,D±101(α1,α2,α3)=eiα1sin(α2)/21/2,D0,±11(α1,α2,α3)=eiα3sin(α2)/21/2,D111(α1,α2,α3)=ei(α1+α3)cos2(α2/2),D111(α1,α2,α3)=ei(α1+α3)cos2(α2/2),D111(α1,α2,α3)=ei(α1α3)sin2(α2/2),D111(α1,α2,α3)=ei(α1α3)sin2(α2/2).
(12)

As one can check by algebraic manipulation, the above ninefold-degenerate set of eigenfunctions can be put into one-to-one correspondence with the elements of R. That is, it is possible to find linear combination coefficients cpqmm such that
Rpq=m,m=11cpqmmDmm1(R),
(13)
where Rpq are the elements of R. Thus, if eigenfunctions of ΔB could be accessed by processing the observed snapshots aR on the data manifold, e.g., through one of the graph-theoretic algorithms developed in machine learning [7

7. M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput. 13, 1373–1396 (2003). [CrossRef]

, 10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

], Eq. (13) could be used to invert the embedding map Φ. This would be tantamount to having learned to “navigate” on the data manifold.

The method outlined above for symmetry-based inversion of Φ is also applicable under weaker symmetry conditions on the metric. In particular, it can be extended to certain metrics of the form
h=1E1E1+2E2E2+3E3E3,
(14)
where Eμ are the right-invariant dual basis vectors in Eq. (39), and μ are non-negative parameters. These are the so-called spinning-top metrics of classical and quantum-mechanical rotors [36

36. L. C. Biedenharn and J. D. LouckAngular Momentum in Quantum Physics (Addison Wesley, 1981).

,51

51. J. L. McCauleyClassical Mechanics: Transformations, Flows, Integrable and Chaotic Dynamics (Cambridge University Press, 1997).

], arising also in homogeneous cosmological models of general relativity [38

38. B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D 8, 1048–1060 (1973). [CrossRef]

,39

39. A. H. Taub“Empty space-times admitting a three parameter group of motions,” Ann. Math. 53, 472–490 (1951). [CrossRef]

,52

52. C. Misner“Mixmaster universe,” Phy. Rev. Lett. 22, 1071–1074 (1969). [CrossRef]

]. In classical and quantum mechanics, h features in the Hamiltonian of a rotating rigid body with principal moments of inertia given by μ. In general relativity, μ characterize the anisotropy of space in the so-called mixmaster cosmological model [52

52. C. Misner“Mixmaster universe,” Phy. Rev. Lett. 22, 1071–1074 (1969). [CrossRef]

].

By construction, metrics in this family are invariant under arbitrary right multiplications, i.e., they possess an SO(3) isometry group. This is sufficient to make (𝒮,h) a Riemannian homogeneous space. If two of the μ parameters are equal (e.g., 1 = 2), h describes the motion of an axisymmetric rotor, or the spatial structure of the Taub solution in general relativity [39

39. A. H. Taub“Empty space-times admitting a three parameter group of motions,” Ann. Math. 53, 472–490 (1951). [CrossRef]

]. As one may explicitly verify, in addition to being invariant under left multiplications, the metric of the axisymmetric rotor is invariant under translations from the left by the one-parameter subgroup associated with rotations about the axis of symmetry, which corresponds here to the direction of the incoming scattering beam. Therefore, it has a larger, SO(3) × SO(2) isometry group than the more general metric of an asymmetric rotor. In the special case that all of the μ are equal, h reduces to a multiple of the round metric B in Eq. (9).

Let Δh denote the Laplace-Beltrami operator associated with h. It is possible to verify that Δh, and the Laplacian ΔB corresponding to the round metric commute. That is, it is possible to find eigenfunctions that satisfy the eigenvalue problem for ΔB and Δh simultaneously. In particular, as Hu [38

38. B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D 8, 1048–1060 (1973). [CrossRef]

] shows, the eigenvalue-eigenfunction pairs ( λmj, ymj) of Δh can be expressed as linear combinations of Wigner D-functions with the same j and m quantum numbers:
ymj=m=jjAmmjDmmj,
(15)
for some linear expansion coefficients Ammj. For the most general metrics with 123, no closed-form expression is available for either Ammj, or the corresponding eigenvalues λmj. However, in the special case of axisymmetric rotors, any Ammj in Eq. (15) will produce an eigenfunction of Δh. This means that the vector space spanned by the j = 1 eigenfunctions associated with the metric of an axisymmetric rotor (denoted here by ymmj) is nine-dimensional. In particular, Eq. (13) can be applied directly with Dmm1 replaced by ymm1.

The eigenvalue λmj corresponding to ymmj in the so-called prolate configuration, 1 = 23, is given by
λmj=121j(j+1)(121123)m2,
(16)
with a similar formula for the oblate configuration 1 = 23 [38

38. B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D 8, 1048–1060 (1973). [CrossRef]

]. An important point about Eq. (16) (and its oblate analog) is that all of the j = 1 eigenvalues are greater than zero and smaller than the maximal j = 2 eigenvalue; i.e., the j = 1 eigenfunctions can be identified by ordering the eigenvalues. This property, which does not apply for general asymmetric-rotor metrics, alleviates the difficulty of identifying the correct subset of eigenfunctions for orientation recovery via Eq. (13).

4.4. Accessing the leading Laplacian eigenfunctions of the homogeneous metric

The method outlined above for symmetry-based inversion of Φ makes direct use of the fact that (𝒮,h) is a Riemannian homogeneous space. However, (𝒮,h) is generally inaccessible to numerical algorithms, which access a discrete subset of the manifold equipped with the induced metric g, i.e., (𝒮,g). For our purposes, it is important to establish the isometries of g, because the latter govern the behavior of the Laplacian eigenfunctions computed via graph-theoretic algorithms [5

5. J. B. Tenenbaum, V. de Silva, and J. C. Langford“A global geometric framework for nonlinear dimensionality reduction,” Science 290, 2319–2323 (2000). [CrossRef] [PubMed]

7

7. M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput. 13, 1373–1396 (2003). [CrossRef]

, 9

9. R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. Zucker“Geometric diffusions as a tool for harmonic analysis and structure definition on data,” Proc. Natl. Acad. Sci. U.S.A. 102, 7426–7431 (2005). [CrossRef] [PubMed]

, 10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

].

In general, g is not invariant under arbitrary left or right multiplications. The lack of invariance of g under the right multiplication map RQ can be seen by considering its components in a right-invariant basis. In particular, it can be shown that RQ is an isometry of g if and only if the components gμν in the right-invariant basis from Eq. (7) are invariant under replacing R by RQ, which does not hold generally. What about the behavior of g under left multiplications? Here, an expansion of g in an analogous left-invariant basis reveals that g is not invariant under left multiplications by general SO(3) matrices, but is invariant under left multiplication by a rotation matrix Q about the beam axis z (see Fig. 2). This is intuitively obvious, because the outcome of replacing a snapshot aR with aQR is then a rotation on the detector plane, which has no influence on the value of the L2 inner product used to evaluate g. In summary, instead of the six-dimensional SO(3) × SO(3) isometry group of B, the isometry group of the induced metric is the one-dimensional SO(2) group of rotations about the beam axis, which obviously cannot act transitively on the three-dimensional latent manifold.

Despite the insufficiency of g to make (𝒮,g) a Riemannian homogeneous space, g admits a decomposition of the form
g=h+w,
(17)
with the following properties: (1) h is a spinning-top metric from Eq. (14) with 1 = 2 (i.e., an axisymmetric-rotor metric, not an arbitrary right-invariant metric); (2) w is a symmetric (but not necessarily positive-definite) tensor, whose components average to zero over the manifold, describing the inhomogeneous part of g (see Appendix A.2 for a derivation). Property (1) is a direct consequence of projection onto a circularly-symmetric 2D detector, and therefore an essential aspect of scattering experiments.

The important point is this: scattering manifolds are associated with induced metrics g, which, in themselves, possess low symmetry. But they can be decomposed into a homogeneous part h with a high SO(2) × SO(3) symmetry and thus associated with well-known Laplacian eigenfunctions independently of the object, plus a low-symmetry residual w, which depends on the object. In general, there is no guarantee that the magnitude of w relative to h [measured, e.g., through the tensor norm in Eq. (56)] is small for arbitrary objects. However, as we demonstrate in Sec. 5.2, certain results pertaining to g can be well-approximated by symmetry-based analytical results for h, even if the norm of w is significant. For the purposes of the orientation-recovery scheme proposed here, the key properties in question are the leading eigenfunctions of the Laplace-Beltrami operator Δg associated with the induced metric in Eq. (5). These eigenfunctions control the late-time evolution of the heat kernel (i.e., the fundamental solution to the heat equation), which is in turn governed by the topological properties of the data manifold [47

47. P. H. BérardSpectral Geometry: Direct and Inverse Problems, (Springer-Verlag, 1989).

, 48

48. S. RosenbergThe Laplacian on a Riemannian Manifold (Cambridge University Press, 1997). [CrossRef]

]. Consequently, the leading-order eigenfunctions are highly robust against changes of metric. It is therefore natural to design algorithms that employ the leading eigenfunctions of Δg as a set of basis functions to expand the j = 1 eigenfunctions of Δh, as described below.

Represent each snapshot aRi in the dataset as a point in nine-dimensional Euclidean space ℝ9 with coordinates given by (ψi1,...,ψi9). Here, ψik are eigenvector components of a diffusion operator on a graph constructed from the s observed snapshots (aR1,..., aRs) in n-dimensional data space (see Appendix B). This induces an embedding Ψ of the latent manifold 𝒮 in ℝ9 given by
Ψ(Ri)=(ψi1,,ψi9).
(18)
Provided that the number of observed snapshots is sufficiently large, suitable algorithms (such as Diffusion Map of Coifman and Lafon [10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

, 53

53. S. Lafon“Diffusion maps and geometric harmonics,” Ph.D. thesis, Yale University (2004).

]), lead to embedding coordinates ψik, which converge to the corresponding values of the Laplacian eigenfunctions associated with g, even if the sampling of the data manifold is non-uniform. More specifically, for large-enough s we have the correspondence
ψikψk(Ri),
(19)
where ψk(Ri) is the k-th eigenfunction of Δg, i.e.,
Δgψk=λkψk
(20)
with
Δg()=|g|1/2μ,ν=1mμ[|g|1/2gμνν()].
(21)

The symmetries of h play an essential role in this procedure, since they yield: (1) the number and sequence of graph-Laplacian eigenfunctions used to represent the latent manifold in Eq. (18); and (2) the procedure to infer the orientations Ri from the eigenfunctions [in particular, via the structure of the error functional in Eq. (62a)]. In essence, one can regard the homogeneous metric h as an object-independent “Platonic ideal” [54

54. W. D. RossPlato’s Theory of Ideas (Oxford University Press, 1951). [PubMed]

] version of g, and develop algorithms, which make use of the properties of h to analyze general scattering datasets. In Sec. 5.2, we demonstrate accurate orientation recovery by using the leading-order Laplace-Beltrami eigenfunctions. This approach is particularly attractive for biological objects, which are generally weak scatterers of low symmetry. (The case of strongly symmetric objects will be treated elsewhere.) As expected from the robustness of the leading eigenfunctions, orientation recovery and object reconstruction are possible even when the induced metric g differs significantly from the axisymmetric-rotor metric, as quantified by the Lipschitz constant [Eq. (24)]. The symmetries of h can also be exploited to enforce appropriate constraints in Bayesian algorithms [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

].

4.5. Extension to general scattering problems

Because the above analysis was performed under a restrictive set of experimental conditions, we now consider the effect of removing these. The assumption of kinematic (single) scattering introduces an additional symmetry due to Friedel’s law. As we have not used this symmetry, our arguments remain valid under multiple scattering conditions. The use of linearly or elliptically polarized radiation introduces a second preferred direction in addition to that of the beam, thus removing the SO(2) isometry under left translations, but this can be restored by appropriate correction with the polarization factor. A detector not at right angles to the beam axis also reduces the isometry to I × SO(3), but this can also be easily corrected by an appropriate geometric factor. Absorption can be accommodated as a complex density function, inelastic scattering by allowing q1q2, etc. Neither affects our conclusions. Our approach is thus applicable to a wide range of image formation modalities. Later in this paper and in Paper II, we demonstrate the validity of our approach in the context of X-ray diffraction snapshots and cryo-EM micrographs of biological molecules, and optical images of macroscopic objects. Only in the last example does multiple scattering play a significant role. We recognize, however, the importance of problems, such as those involving microwaves [55

55. K. Belkebir and M. Saillard“Testing inversion algorithms against experimental data: Inhomogeneous targets,” Inverse Probl. 21, S1 (2004). [CrossRef]

, 56

56. J. M. Geffrin and P. Sabouroux“Continuing with the Fresnel database: Experimental setup and improvements in 3D scattering measurements,” Inverse Probl. 25, 024001 (2009). [CrossRef]

], where multiple scattering is dominant. The demonstration of applications in this domain remains a future task.

We note that our approach has to be modified when the object has discrete or continuous symmetries. This is because the data manifold in this case is not SO(3), but the quotient space SO(3)/Γ where Γ is a subgroup of SO(3) representing the object’s symmetries. Among the eigenfunctions of the Laplacian on the SO(3) manifold, only those that are constant on Γ “survive” in the SO(3)/Γ environment. Thus, the orientation recovery procedure must be modified depending on the form of the available eigenfunctions. This issue will also be addressed elsewhere.

5. Demonstration of structure recovery in 3D

It has long been known that the use of problem-specific constraints can substantially increase computational efficiency [57

57. Y. LeCun, J. S. Denker, S. Solla, R. E. Howard, and L. D. Jackel“Optimal brain damage,” in Advances in Neural Information Processing Systems (NIPS 1989), D. Touretzkyed. (Morgan Kaufman, 1990), Vol. 2, pp. 598–605.

]. By combining wide applicability with class specificity, symmetries represent a particularly powerful example of such constraints. Exploiting these, we here demonstrate successful orientation recovery for a system computationally 104× more complex than previously attempted [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

,23

23. N. T. D. Loh and V. Elser“Reconstruction algorithm for single-particle diffraction imaging experiments,” Phys. Rev. E 80, 026705–1–026705–20 (2009). [CrossRef]

]. In Paper II we apply our framework to simulated and experimental snapshots of various kinds with extremely low signal.

5.1. 3D reconstruction from diffraction snapshots with high computational complexity

We simulated X-ray snapshots of the closed conformation of E. coli adenylate kinase (ADK; PDB descriptor 1ANK) in different orientations to a spatial resolution d = 2.45 Å, using 1 Å photons. In this calculation, Cromer-Mann atomic scattering factors were used for the 1656 non-hydrogen atoms [58

58. D. T. Cromer and J. B. Mann“Atomic scattering factors computed from numerical Hartree-Fock wavefunctions,” Acta Cryst. A 24, 321–324 (1968). [CrossRef]

], neglecting the hydrogen atoms. We discretized the diffraction patterns on a uniform grid of n = 126 × 126 = 15,876 detector pixels of appropriate (Shannon) size, taking the corresponding orientations on SO(3) according to the algorithm in Ref. [59

59. L. Lovisolo and E. A. B. da Silva“Uniform distribution of points on a hyper-sphere with applications to vector bit-plane encoding,” IEE Proc. Vision Image Signal Process. 148, 187–193 (2001). [CrossRef]

]. The number of diffraction patterns required to sample SO(3) adequately is given by 8π2(D/d)3 ≈ 8.5 × 105, where D = 54 Å is the diameter of the molecule [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

]. In our simulation, however, a larger D = 72 Å diameter was assumed, allowing, e.g., for the possibility to reconstruct the structure of ADK’s open conformation. Hence, a total of s = 2 × 106 patterns were used in the present analysis.

The diffraction patterns were provided to our Diffusion Map-based algorithm with no orientational information, and the orientation of each diffraction pattern was determined by means of the algorithm described in Appendix B, executed with the following parameters: number of nearest neighbors in the sparse distance matrix d = 220; Gaussian kernel bandwidth ε = 1 × 104; number of datapoints for least-squares fitting r = 8 × 104. To estimate the difference between the deduced and true orientations, respectively represented by unit quaternions τ̃i and τi [see Eq. (66)], we used the RMS internal angular distance error,
ɛ=[1s(s1)ij(D˜ijDij)2]1/2.
(23)
In the above, Dij = 2 arccos(|τi ·τj|) and D̃ij = 2 arccos(|τ̃i ·τ̃j|) are respectively the true and estimated internal distances between orientations Ri and Rj, and · is the inner product between quaternions. The resulting internal angular distance error in the present calculation was 0.8 Shannon angles.

Next, we placed the diffracted intensities onto a uniform 3D Cartesian grid by “cone-gridding” [60

60. P. Schwander“Efficient interpolation of scattering data to an arbitrary grid,” (in preparation, 2012).

], and deduced the 3D electron density by iterative phasing with a variant of the charge flipping technique [18

18. F. Oszlányi and A. Süto“Ab initio structure solution by charge flipping,” Acta Crystallogr. 60, 134–141 (2004). [CrossRef]

] developed by Marchesini [61

61. S. Marchesini“Ab initio compressive phase retrieval,” presented at the XXI IUCr Congress, Osaka, Japan, 23–31 Aug. 2008.

]. Charge flipping was prevented outside a spherical support about twice the diameter of the molecule. The R-factor between the gridded scattering amplitudes and the ones obtained from phasing was 0.19. The close agreement with the correct structural model is shown in Fig. 3 and the movie [14].

Fig. 3 Three-dimensional electron density of the closed conformation of E. coli adenylate kinase, recovered from 2×106 diffraction patterns of unknown orientation at 2.45 Å resolution. Hydrogen atoms were neglected in the electron density calculation. The ball-and-stick model represents the actual structure. See also the movie [14].

5.2. Robustness against metric inhomogeneity

As discussed in Sec. 4.4 above, the accuracy of our proposed orientation recovery scheme relies on the leading nine Laplacian eigenfunctions ψk associated with the inhomogeneous metric g being good approximations of the nine j = 1 eigenfunctions ymj of Eq. (15) associated with some axisymmetric rotor metric h [Eq. (14) with 1 = 2]. This is a significantly weaker condition than requiring that the metrics themselves be close, or, equivalently, that a suitably-defined norm ‖wh quantifying the importance of the inhomogeneous term w in Eq. (17) relative to h be small, as we now demonstrate.

A natural way of quantifying the closeness of g to axisymmetric rotor metrics is through Lipschitz constants, defined as the smallest constants Λ, Λ+ ≥ 1 meeting the condition
1Λ2h(v,v)g(v,v)Λ+2h(v,v),
(24)
for all tangent vectors v and points on the data manifold [62

62. P. Bérard, G. Besson, and S. Gallot“Embedding Riemannian manifolds by their heat kernel,” Geom. Funct. Anal. 4, 373–398 (1994). [CrossRef]

]. These constants (which do not necessarily exist for arbitrary pairs of metrics) bound the distortion in neighborhood distances determined from g relative to the corresponding distances measured with respect to h, with Λ, Λ+ ≈ 1 corresponding to small distortion.

We have used atomic positions and structure factors (known a priori for the simulated data used in this paper) to evaluate the components gμν (R) in a right-invariant basis through Eq. (7), without having to perform finite-difference differentiation. In that basis, a general axisymmetric rotor metric is represented by an R-independent diagonal matrix [hμν] = K diag(, , 1), where = 1/3 is an anisotropy parameter, and K a scaling factor controlling the volume of the data manifold. As described in Appendix A.3, Λ and Λ+ may be determined by solving a generalized eigenvalue problem associated with gμν (R) and hμν for every orientation R in the data set. Moreover, it is possible to introduce a norm ‖·‖h with the properties that: (1) ‖hh = 1 by construction; and (2) ‖wh is bounded from below through the upper Lipschitz constant:
whΛ+1.
(25)
Thus, w is negligible compared to h only if Λ+ − 1 ≪ 1. (See Appendix A.4 for details.)

First, we assess the discrepancy between g and the closest axisymmetric rotor metric, which imparts the same volume to the data manifold as g. That is, we vary to minimize Λ = max{Λ, Λ+}, with K chosen such that ∑i det[gμν (Ri)]1/2 = s det[hμν]1/2. (The sum runs over the s samples in the data set.) The results of this calculation for ADK and chignolin molecules (the latter studied in Paper II) are (Λ, Λ+) = (1.20, 1.21) and (1.52, 1.41), respectively. This means that the norm ‖wh of the inhomogeneous term relative to h is at least 0.21 and 0.41 for these two objects, i.e., non-negligible.

Next, in order to assess the impact of inhomogeneity on the eigenfunctions used for orientation recovery, we compute the distance γ between the vector space Vg spanned by the leading nine eigenvectors ψ1,...,ψ9 determined through graph-theoretic analysis and the corresponding space Vh spanned by the leading nine eigenfunctions of the Laplace-Beltrami operator Δh associated with the axisymmetric rotor metric h, evaluated at the known orientations Ri. A standard measure of that distance from linear algebra is [63

63. G. W. Stewart“Error and perturbation bounds for subspaces associated with certain eigenvalue problems,” SIAM Rev. 15, 727–764 (1973). [CrossRef]

]
γ=ΠgΠh2,
(26)
where Πg and Πh are orthogonal projectors from ℝs (the space spanned by all eigenfunctions of a data set with s samples) to Vg and Vh, respectively, and ‖·‖2 denotes the spectral norm of matrices (recall that ‖A2 is equal to the largest singular value of A).

The γ distance measure lies in the interval [0, 1], and may be interpreted as the sine of an angle characterizing the deviation of Vg from Vh. For the ADK and chignolin data sets, the eigenvectors computed via the Diffusion Map algorithm [10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

] (see Appendix B) lead to γ = 0.0017, and γ = 0.0023, respectively. Thus, the empirical eigenfunctions provide a highly accurate basis to expand the j = 1 eigenfunctions of Δh via Eq. (22), despite the fact that the corresponding inhomogeneous terms are significant (as measured via ‖wh). We expect that similar values of Λ±, and correspondingly high accuracy of orientation recovery apply to a wide range of objects. Of course, it is possible that some objects, e.g., those with large aspect ratios, may lead to induced metrics with significantly larger Lipschitz constants, and more significant discrepancies between the empirical and symmetry-based eigenfunctions. These instances, which lie outside the scope of the present paper, may become amenable to our approach after suitable homogenization techniques, such as numerical Ricci flow [64

64. H.-D. Cao and X.-P. Zhu“Hamilton-Perelman’s proof of the Poincaré conjecture and the geometrization conjecture,” (2006). arxiv:math/0612069v1 [math.DG].

, 65

65. P. ToppingLecture Notes on Ricci Flow (Cambridge University Press, 2006). [CrossRef]

].

5.3. Computational cost

In the absence of orientational information, the computational cost C of orientation recovery without restrictive sparsity assumptions scales as a power law
CR8=(D/d)8,
(27)
with D the object diameter and d the spatial resolution [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

24

24. P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys. 12, 1–15 (2010). [CrossRef]

]. The analysis of ADK was performed with R = 30, compared with the largest previously published value of R ≤ 8 [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

24

24. P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys. 12, 1–15 (2010). [CrossRef]

]. This represents an increase of four orders of magnitude in computational complexity over the state of the art, as shown below.

The computational cost of a single expectation-maximization (EM) step in Bayesian algorithms (e.g., the GTM algorithm [29

29. C. M. Bishop, M. Svensen, and C. K. I. Williams“GTM: The generative topographic mapping,” Neural Comput. 463, 379–383 (1998).

, 66

66. J. F. M. Svensen“GTM: The generative topographic mapping,” Ph.D. thesis, Aston University (1998).

]) scales as Ksn, where K, s, and n are the number of quaternion nodes, the number of snapshots, and the data-space dimension, respectively [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

]. Here, the data space dimension is equal to the number of Shannon pixels. Assuming an over-sampling of 2 in each linear dimension, we have
K=8π2S(Dd)3,s=fK=8π2fS(Dd)2,n={4Dλtan[2arcsin(λ2d)]}216(Dd)2,
(28)
where S is the object symmetry, f the number of snapshots per orientational bin, and λ the wavelength. Assuming that the number of EM iterations is constant, Fung, Shneerson, Saldin, and Ourmazd (FSSO) [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

] estimate an eighth-power scaling of the form in Eq. (27) for the total computational cost of orientation recovery with GTM. The fact that GTM is NP-hard remains moot.

Loh and Elser (LE) [23

23. N. T. D. Loh and V. Elser“Reconstruction algorithm for single-particle diffraction imaging experiments,” Phys. Rev. E 80, 026705–1–026705–20 (2009). [CrossRef]

] argue that their EM-based approach scales as
CMrotsNphotons,
(29)
where Mrot is the number of rotation samples (orientational bins), and that this leads to an R6 scaling. This is based on three assumptions: (1) A sparse formulation can be used to replace the number of detector pixels n with a much smaller number of scattered photons Nphotons; (2) Nphotons does not depend on R, and thus can be ignored in the scaling behavior; (3) The number of EM iterations is independent of R (as in Ref. [22

22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

]), and of Nphotons. Note that Mrot and the number of GTM bins, K, are equal.

Assumption (1) holds only for very small photon counts and in the absence of significant background scattering. Assumption (2) is not justified [67

67. V. L. Shneerson, A. Ourmazd, and D. K. Saldin“Crystallography without crystals. I. the common-line method for assembling a 3D diffraction volume from single-particle scattering,” Acta Cryst. A 64, 303–315 (2008). [CrossRef]

]. For a globular protein, the total number of photons scattered to large angle scales linearly with the number of non-H atoms, and hence object volume, i.e., as D3. Thus,
Mrot=8π2S(Dd)3,s=8π2fS(Dd)2,Nphotonsn=16(Dd)2,
(30)
leading to the same R8 scaling behavior as FSSO. The validity of assumption (3) remains moot.

Equipped with the estimates from Eqs. (27)(30), we now compare the computational complexity of our ADK calculation with the reconstructions of the chignolin and GroEL molecules by FSSO and LE, respectively (Table 1). Using Eq. (27), the increase in computation complexity on going from chignolin (Dchig = 16 Å, dchig = 1.8 Å), to ADK (DADK = 54 Å, DADK (support) = 72 Å, dADK = 2.45 Å) is
(DADK(support)/dADKDchig/dchig)8=(29.48.9)8=1.4×104.
(31)
Using the scaling expression of Eq. (29), the increase in complexity on going from GroEL to ADK (72 Å support) for the Loh & Elser algorithm varies between O(103) and O(104) for sparse and non-sparse representations, respectively (Table 1). As a sparse representation is not generally possible and we have not had to resort to it, the appropriate comparison is 104.

Table 1. Computational complexity of orientational recovery for GroEL and ADK

table-icon
View This Table
| View All Tables

We conclude this section by addressing the issue of uniqueness. The non-convex least-squares fit used to deduce orientations from the leading eigenfunctions of the embedding constitutes a non-deterministic step in our procedure. It is thus possible that the resulting solution corresponds to a local minimum. The correctness of this solution, however, can be checked as follows. By Eq. (16), the first nine eigenfunctions of the axisymmetric top metric appear as sixfold and three-fold degenerate sets. The latter set with m = 0 (and only this set) defines an S2 [i.e., a spherical shell; see Eq. (12)], with each point on the surface defining the beam direction for a snapshot in the molecular frame. It is thus straightforward to determine two of the three angles specifying the particle orientation. The third angle corresponds to a rotation about the axis defined by the other two angles, and can be determined by angular correlation between different snapshots. This procedure can be used as an independent check on the correctness of the solution obtained by the least-squares fit.

6. Conclusions

As shown in Paper II, the manifold itself offers a powerful route to image reconstruction at extremely low signal, because snapshots reconstructed from the manifold achieve higher signal-to-noise ratios than can be obtained by traditional methods relying on classification and averaging. Combined with the ability to sort random snapshots of an evolving system into a time-series, also demonstrated in Paper II, our approach offers a radically new way for studying dynamic systems in 4D, with immediate applications to data from X-ray Free Electron Lasers and electron microscopy. Fundamentally, the homogeneous metric describes the transformations of objects without reference to any specific object. This is reminiscent of a Platonic Form, from which specific objects emanate [54

54. W. D. RossPlato’s Theory of Ideas (Oxford University Press, 1951). [PubMed]

]. It is therefore tempting to regard the homogeneous manifold as a Platonic Form, from which our perception of three-dimensional objects stems [68

68. W. HeisenbergDer Teil und das Ganze (R. Piper & Co.Verlag, 1981).

].

A. The induced metric tensor of scattering data sets

Here, we discuss the properties of the induced metric tensor g in Eq. (5). We begin in Appendix A.1 with a derivation of the explicit form for the components of g in the right-invariant basis from Eq. (7). In Appendix A.2 we perform the decomposition of g in Eq. (17) into axisymmetric (h) and inhomogeneous (w) parts. In Appendices A.3 and A.4 we describe the evaluation of the Lipschitz constants between g and h, and discuss how the latter can be used to place a lower bound on a norm for w relative to h.

A.1. Derivation

Following Sec. 4.2, we describe scattering as an embedding Φ taking the latent manifold 𝒮 to the set of square-integrable intensity patterns L2(ℝ2) on a 2D dimensional detector. Broadly speaking, the induced metric describes an inner product between tangent vectors on the latent manifold 𝒮 associated with that embedding. More specifically, in accordance with Eq. (5), that inner product is computed by “pushing forward” tangent vectors on 𝒮 to manifest space, and applying the canonical Hilbert space inner product in Eq. (3). The map carrying along the tangent vectors of 𝒮 is the derivative map Φ* associated with Φ, which is evaluated as follows.

First, note that every smooth tangent vector field v on 𝒮 generates a corresponding one-parameter family of transformations [33

33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

, 34

34. S. LangIntroduction to Differentiable Manifolds (Springer-Verlag, 2002).

, 41

41. A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).

],
ϕα(R)=Rα,
(32)
with α a scalar parameter and Rα an element of 𝒮, which depends smoothly on α. In the above, ϕα describes a curve on the manifold (called an integral curve of v), which is tangent to v at every point.

Likewise, the pushforward Φ*(v) of v is associated with a continuous transformation ϕ̃α of intensity snapshots in manifest space. Denoting the snapshot associated with orientation R by aR = Φ(R), that transformation is given by
ϕ˜α(aR)=aRα
(33)
with aRα determined from Eq. (32). The outcome of acting on v with Φ* is then the directional derivative of intensity snapshots along the path defined by ϕ̃α, viz.
Φ*(v)=limα0aRαaRα.
(34)

The induced metric g resulting from the above procedure will depend on the explicit form of the embedding map Φ. Here, we consider the case where Φ describes far-field kinematic elastic scattering from a single object, where intensity amplitudes are given by the Fourier integral in Eq. (1). Other scattering scenarios can be treated in a similar manner, provided that Φ meets the conditions of an embedding. For our purposes, it is sufficient to consider one-parameter transformations arising from left multiplication by SO(3) matrices carrying out rotations about one of the x, y, or z axes [see Eq. (8)]. That is, we set
Lαμ(R)=exp(αJμ)Rforμ{1,2,3},
(35)
where α is the rotation angle in radians, and J1, J2, and J3 are 3 × 3 antisymmetric matrices generating rotations about the x, y, and z axes:
J1=(000001010),J2=(001000100),J3=(010100000).
(36)
We denote the vector fields generating ϕαμ by eμ. It then follows from Eq. (34) with Rα=Lαμ(R) that the pushforward fields Φ*(eμ) are given by
Φ*(eμ)(r)=[ω(r)]1/2[JμqaR(q)]|q=q(r).
(37)
Note that in deriving Eq. (37) we have used the divergence-free property · (Jμq) = 0, which applies for any scattering wavevector q and rotation generator Jμ.

As one may verify, the tangent vector fields eμ are linearly independent. This means that the set {e1, e2, e3} forms a basis to expand tangent vectors on 𝒮, and, in turn, the induced metric can be represented by a 3 × 3 matrix with elements
gμν(R)=(Φ*eμ,Φ*eν).
(38)
The gμν (R) above are the components of the induced metric in Eq. (6) at orientation R, provided that Eμ are dual basis vectors to eν, defined through the relation
Eμ(eν)=δμν.
(39)
Moreover, it is possible to show that eμ are invariant under the right multiplication map RQ in Eq. (8) [46

46. R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).

]. Substituting for Φ*(eμ) in Eq. (38) using Eq. (37) then leads to the expression in Eq. (7) for the components of the induced metric in a right-invariant tensorial basis.

Besides the form in Eq. (7), it is useful to express the components of g in terms of spherical harmonics in reciprocal space. As is customary in diffraction theory [69

69. D. Saldin, V. L. Shneerson, R. Fung, and A. Ourmazd“Structure of isolated biomolecules obtained from ultrashort X-ray pulses: Exploiting the symmetry of random orientations,” J. Phys.: Condens. Matter 21, 134014 (2009). [CrossRef]

], we write down the reference scattering amplitude a = Φ(I) corresponding to the identity matrix I using the expansion
a(q)=j=0m=jjajm(q)Yjm(θ,ϕ),
(40)
where ajm are complex functions of the radial coordinate q in reciprocal space, and Yjm are spherical harmonics. Note the property ajm*=(1)majm, which is a consequence of a(q) being real. Making use of the standard formula describing rotations of spherical harmonics via Wigner D-matrices,
Yjm(R1(θ,ϕ))=m=jjDmmj(R)Yjm(θ,ϕ),
(41)
it follows that the amplitude distribution aR = Φ(R) corresponding to object orientation R is given by
aR(q)=j=0m,m=jjajm(q)Dmmj(R)Yjm(θ,ϕ).
(42)
Inserting the above in Eq. (7) leads to the following general expression for the metric components,
gμν(R)=j1,j2=0m1,m1=j1j1m2,m2=j2j2(1)m1+m1Dm1,m1j1(R)Dm2,m2j2(R)Kμνj1m1m1j2m2m2,
(43)
In the above, Kμνj1m1m1j2m2m2 are complex-valued coefficients, which vanish unless the following conditions are met (together with the corresponding conditions obtained by interchanging μ and ν):
m2=m1±2orm2=m1for(μ,ν)={(1,1),(2,2),m2=m1±2for(μ,ν)=(1,2),m2=m1±1for(μ,ν)={(1,3),(2,3),m2=m1for(μ,ν)=(3,3).
(44)

A.2. Decomposition into homogeneous and inhomogeneous parts

Even though the induced metric tensor g in Eq. (5) is not homogeneous, it is nevertheless possible to decompose it as a sum
g=h+w,
(45)
where h is a homogeneous metric with respect to a group acting transitively on the data manifold, and w a tensor that averages to zero over the manifold. Using Fourier theory on SO(3) [37

37. G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]

, 70

70. P. Kostelec and D. Rockmore“FFTs on the rotation group,” Santa Fe Institute working paper #03-11-060 (2003).

], here we compute the components of h and w in the right-invariant basis Eμ from Eq. (39). The analysis presented below yields the important results that (i) the homogeneous part h of the metric belongs to the family of metrics associated with axisymmetric rotors; (ii) the Fourier spectrum of w has a highly sparse structure, with only a limited number of nonzero coefficients contributing to metric inhomogeneity.

We begin by noting that the Fourier transform of the metric components gμν in Eq. (43) consists for each (μ,ν) of the sequence {g^μ,νj}j=0 of (2j + 1) × (2j + 1) matrices gμνj, whose components are given by
[g^μνj]mm=dV(R)gμν(R)Dmmj(R1).
(46)
In the above, integration is performed over SO(3) using the volume element dV of the bi-invariant metric B in Eq. (9), and Dmmj are the Wigner D-functions from Eq. (11). An explicit formula for the volume element associated with B (the Haar measure), expressed in terms of the zyz Euler angles (α1, α2, α3) parameterizing a rotation matrix R, is dV (R) = |B|1/21 2 3 with |B| = (det[Bμν])1/2 = sin(α2). The collection of the g^μνj matrices in Eq. (46) may be used to recover g′(R) via the inverse transform
gμν(R)=18π2j=0(2j+1)tr(g^μνjDj(R)),
(47)
where Dj(R)=[Dmmh(R)] is the j-th Wigner matrix of size (2j + 1) ×(2j + 1). Because D0 is the trivial representation of SO(3), a constant scalar on the manifold, the term g^μν0 corresponds to the homogeneous part of the metric. The g^μνj with j ≥ 1 give rise to the inhomogeneous tensor w, which encodes object-specific information. That is, we have
hμν=g^μν0,wμν=18π2j=1(2j+1)tr(g^μνjDj(R)).
(48)
where hμν and wμν are the components of h and w in the Eμ basis, respectively.

Since each component of the metric contains a product of two Wigner D-functions [see Eq. (43)], the calculation of the Fourier transform is facilitated significantly by the triple-integral formula involving the 3- jm symbols of quantum mechanical angular momentum [37

37. G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]

, 50

50. D. A. Varshalovich, A. N. Moskalev, and V. K. KhersonskiiQuantum Theory of Angular Momentum (World Scientific, 1988).

],
dV(R)Dmmj*(R)Dm1m1j1(R)Dm2m2j2(R)=(1)m+m8π2(j1j2jm1m2m)(j1j2jm1m2m).
(49)
In particular, inserting the metric components from Eq. (43) in Eq. (46), and making use of the triple-integral formula, leads to the result
[g^μνj]mm=j1=0j2=|j1j|j1+jm1,m1=j1j1m2,m2=j2j2Kμνj1m1m1j2m2m2(1)m1+m1+m+m16π2×(j1j2jm1m2m)(j1j2jm1m2m),
(50)
where we have employed the triangle inequality, |j1j2| ≤ jj1 + j2, obeyed by the nonzero 3- jm symbols. The key point about Eq. (50) is that the selection rules for the 3- jm symbols strongly restrict the values of the azimuthal quantum number m for which [g^μνj]mm is non-vanishing. Specifically, it is possible to show that the matrix elements [g^μνj]mm are zero unless
m{0,±2},for(μ,ν)=(1,1)or(μ,ν)=(2,2),m{±2},for(μ,ν)=(1,2),m{±1},for(μ,ν)=(1,3)or(μ,ν)=(2,3),m{0},for(μ,ν)=(3,3).
(51)
It follows that the j = 0 term of the Fourier spectrum (defined only for m = m′ = 0) giving rise to the homogeneous part of the metric has no off-diagonal components. This in turn means that h can be expressed in terms of some non-negative parameters μ in the form of Eq. (14). An explicit evaluation of the on-diagonal terms yields the additional result that the 1 and 2 parameters are, in fact, equal. Thus, the components of the induced metric read
gμν=hμν+wμν,[hμν]=(100010003).
(52)
By construction, the average of wμν over the manifold vanishes, i.e.,
dV(R)wμν(R)=0.
(53)

A.3. Evaluation of the Lipschitz constant

According to Eq. (14), in the right-invariant basis Eμ, a general axisymmetric top metric is represented by a diagonal matrix of the form [hμν] = K diag(, , 1), with > 0 and K > 0. On the other hand, the induced metric g in Eq. (5) is represented by a non-diagonal, symmetric positive matrix with components gμν (R) determined from Eq. (6). In order to compute the Lipschitz constants Λ+ and Λ in Eq. (24), we seek for every orientation R the extrema of the quadratic form g(v,v)=μ,ν=13gμν(R)vμvν, subject to the constraint h(v,v)=μ,ν=13hμνvμvν=1. This problem is equivalent to solving for every R a generalized eigenvalue problem
ν=13gμν(R)vkν=Λk2(R)ν=13hμνvkν
(54)
with k ∈ {1, 2, 3} and Λk > 0, and setting ΛR,+ = max{Λk(R)} and ΛR,− = max{1/Λk(R)}. The Lipschitz constants Λ+ and Λ are then given by the suprema (least upper bounds) of ΛR,+ and ΛR,− over R, respectively. In applications, Λ+ and Λ are estimated through the maxima of ΛR,+ and ΛR,− over a finite set of available orientations {Ri}. This provides a lower bound to the true Lipschitz constants.

As general background, Bérard, Besson, and Gallot [62

62. P. Bérard, G. Besson, and S. Gallot“Embedding Riemannian manifolds by their heat kernel,” Geom. Funct. Anal. 4, 373–398 (1994). [CrossRef]

] derive error bounds for the Laplace-Beltrami eigenfunctions with reference to the Lipschitz constants. In particular, they show that if the Ricci curvatures of two metrics, g and h, with finite Lipschitz constants are bounded from below by some negative constant, then there exist constants ηi(Λ), which go to zero as Λ = max {Λ, Λ+} approaches 1, such that for any orthonormal basis of eigenfunctions {yi}i=1K of Δh, one can associate an orthonormal basis of eigenfunctions {ψi}i=1K of Δg satisfying the bound
ψiyiηi(Λ),
(55)
where ‖·‖ denotes the supremum norm. This means that if one approximates the set of (possibly degenerate) eigenfunctions of Δh with corresponding eigenvalues λ1h,,λKh by the eigenfunctions of Δg with corresponding eigenvalues λ1,...,λK (sorted in increasing order), then the maximum error is bounded from above in a pointwise sense. Here, we do not attempt to derive conditions on the properties of the object needed to guarantee that the Lipschitz constant between g and h is finite.

A.4. The norm of the inhomogeneous term

Given the decomposition in Eq. (17) of the induced metric g into a homogeneous metric h associated with an axisymmetric rotor plus an inhomogeneous term w, it is possible to construct a norm ‖wh of w relative to h with a lower bound determined through the upper Lipschitz constant Λ+ between g and h in Eq. (24). First, note that h induces a norm ‖·‖h on tensors of type (0,2) on the manifold. For a sufficiently smooth tensor field u of type (0,2) that norm is defined as
uh=supR,v(|u(v,v)|h(v,v))1/2,
(56)
where the supremum is taken over SO(3) matrices R and nonzero tangent vectors v on SO(3). Thus, ‖uh involves computing the least upper bound over the manifold and over the nonzero tangent vectors of the relative magnitudes of the quadratic forms u(v,v) and h(v,v). By comparison with the upper bound in Eq. (24), it follows immediately that ‖gh = Λ+ ≥ 1. Next, set u = w = gh, and compute ‖wh = ‖ghh. The reverse triangle inequality of norms,
ghh|ghhh|,
(57)
used in conjunction with the trivial result ‖hh = 1, then leads to the bound in Eq. (25).

B. Algorithms

As an instructive application of the symmetries identified in Sec. 4, we describe an accurate and efficient algorithm for the analysis of scattering datasets. This makes explicit use of the properties of the homogeneous metric h in Eq. (14) to interpret results produced by the Diffusion Map algorithm of Coifman and Lafon [10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

]. As mentioned earlier, and also demonstrated in Paper II, a variety of other manifold algorithms can also be used, all taking advantage of the symmetries underlying datasets produced by scattering. Here, we consider the idealized scenario of noise-free data. This will be relaxed in Paper II, where we extend our approach to deal with snapshots severely affected by Poisson and Gaussian noise.

Instead of a continuous data manifold , experimental data represent a countable subset M of consisting of s identically and independently distributed (IID) samples in n-dimensional data space (with n the number of detector pixels) drawn randomly from a possibly non-uniform distribution on . That is, we have
M={a_1,,a_s},
(58)
where ai = (ai1,..., ain) are n-dimensional vectors of pixel amplitudes (see Fig. 1). As described in Sec. 4.2, the amplitudes are given by aij = aRi (r⃗j), where r⃗j is the position of pixel j in the detector plane, and aRi = Φ (Ri) is the snapshot associated with orientation Ri.

In Ref. [10

10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

] it is shown that it is possible to construct a one-parameter family of diffusion processes (random walks) on the point cloud from Eq. (58), with each process described by an s × s transition probability matrix Pε, such that in the limit ε → 0 and s → ∞ the eigenvectors of Pε converge to the eigenfunctions of the Laplace-Beltrami operator Δg associated with the distance metric in data space [i.e., the induced metric tensor in Eq. (5)]. More specifically, if ψk are s-dimensional column vectors in the eigenvalue problem
Pɛψ_k=λkψ_k,ψ_k=(ψ1k,,ψsk)T,
(59)
then the relation ψikψk(Ri) holds for large-enough s and small-enough ε, where ψk(Ri) is the k-th eigenfunction of Δg in Eq. (21) evaluated at element Ri on the latent manifold.

Central to the efficiency of Diffusion Map is the fact that the transition probability matrix Pε is highly sparse. This is because Pε is constructed by suitable normalizations of a matrix W assigning weights Wij = 𝒦 (ai, aj) via a Gaussian kernel
𝒦(a_i,a_j)=exp(a_ia_j2/ɛ)
(60)
to pairs of snapshots in M, depending on their Euclidean distance in data space. In applications, one typically fixes a positive integer d and for each snapshot ai retains the distances up to its d-th nearest neighbor. Hereafter we denote the index of the j-th nearest neighbor of ai by Nij, and the corresponding distance by Sij = ‖aiaNij‖. Pseudocode for computing Pε given the s × d distance and index matrices, S = [Sij] and N = [Nij], is listed in Table 2.

Table 2. Calculation of the sparse transition probability matrix Pε in Diffusion Map, following Coifman and Lafon [10].

table-icon
View This Table
| View All Tables

Because the eigenfunctions ψk are not exact linear combinations of the Wigner D-functions in Eq. (12), a (real) polar decomposition step may be applied to produce an exact rotation matrix R, given an approximate rotation matrix estimated from the eigenfunction data via Eq. (61). The real polar decomposition is a factorization of a real square matrix R̃ into the product
R˜=RS,
(63)
where R is an orthogonal matrix, and S is symmetric positive-semidefinite matrix.

The nonlinear least-squares step may be adequately performed using only a small subset of the full dataset, consisting of r datapoints drawn randomly from M. For instance, in the results of Sec. 5, where the total number of samples is s = 2 × 106, we use r = 8 × 104 datapoints. We denote the total squared residual of the optimization process by 𝒢*, where 𝒢* is equal to 𝒢({cijk}) in Eq. (62a), with {cijk} given by the minimizer of the error functional.

Besides R, one might additionally require an evaluation of the corresponding coordinates in an SO(3) coordinate chart (e.g., for diffraction-pattern gridding). Depending on the coordinate chart of interest, various techniques are available to perform this procedure stably and efficiently. For instance, the coordinates of R in the unit-quaternion parameterization [42

42. J. B. KuipersQuaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality (Princeton University Press, 2002). [PubMed]

] can be determined by making use of the trace formula
tr(R)=1+cosχ
(64)
and the eigenvector relation
Rn=n,
(65)
where χ is the angle of the rotation represented by R, and n = nx x + ny y + nz z is a unit vector in ℝ3 directed along the corresponding axis of rotation. The unit quaternion τ corresponding to R is given by
τ=(cos(χ/2),sin(χ/2)nx,sin(χ/2)ny,sin(χ/2)nz).
(66)

In outline, our orientation-recovery method consists of the following three basic steps:
  1. Use Diffusion Map to compute the first nine non-trivial eigenfunctions ψ1,...,ψ9 of the diffusion operator Pε;
  2. Determine the linear combination coefficients cijk to transform the ψk eigenvectors to (approximate) rotation matrices by solving the nonlinear least squares problem in Eq. (62);
  3. Use the correspondence in Eq. (61) and polar decomposition [Eq. (63)] to assign a rotation matrix Rl to each observed diffraction pattern, and (optionally) extract the parameters of Rl in the SO(3) parameterization of interest.

A high-level description of the orientation-recovery procedure for noise-free data is given in Table 3.

Table 3. Orientation-recovery for noise-free snapshots using Diffusion Map

table-icon
View This Table
| View All Tables

Before closing this section, we comment briefly on methods for choosing the kernel width ε and the number of retained nearest neighbors d. This is a common issue in manifold-embedding algorithms, and a number of strategies for determining these parameters have been developed in the literature [12

12. A. L. Ferguson, A. Z. Panagiotopoulos, P. G. Debenedetti, and I. G. Kevrekidis“Systematic determination of order parameters for chain dynamics using diffusion maps,” Proc. Natl. Acad. Sci. U.S.A. 107, 13597–13602 (2010). [CrossRef] [PubMed]

, 32

32. R. Coifman, Y. Shkolnisky, F. Sigworth, and A. Singer“Graph Laplacian tomography from unknown random projections,” IEEE Trans. Image Process. 17, 1891–1899 (2008). [CrossRef] [PubMed]

]. Here, we determine ε and d a posteriori, by monitoring the value of the least-squares residual 𝒢*. Specifically, in the applications presented in Sec. 5, we start with a number of nearest neighbors d ∼ 100 and a value of ε of order the mean distance to the (d/2)-th nearest neighbors of the datapoints, and then perform successive refinements of these parameters seeking to minimize 𝒢*.

Acknowledgments

References and links

1.

W. A. Freiwald and D. Y. Tsao“Functional compartmentalization and viewpoint generalization within the macaque face-processing system,” Science 330, 845–851 (2010). [CrossRef] [PubMed]

2.

M. Seibert, T. Ekeberg, F. R. N. C. Maia, M. Svenda, J. Andreasson, O. Jönsson, D. Odić, B. Iwan, A. Rocker, D. Westphal, M. Hantke, D. P. DePonte, A. Barty, J. Schulz, L. Gumprecht, N. Coppola, A. Aquila, M. Liang, T. A. White, A. Martin, C. Caleman, S. Stern, C. Abergel, V. Seltzer, J. Claverie, C. Bostedt, J. D. Bozek, S. Boutet, A. A. Miahnahri, M. Messerschmidt, J. Krzywinski, G. Williams, K. O. Hodgson, M. J. Bogan, C. Y. Hampton, R. G. Sierra, D. Starodub, I. Andersson, S. Bajt, M. Barthelmess, J. C. H. Spence, P. Fromme, U. Weierstall, R. Kirian, M. Hunter, R. B. Doak, S. Marchesini, S. P. Hau-Riege, M. Frank, R. L. Shoeman, L. Lomb, S. W. Epp, R. Hartmann, D. Rolles, A. Rudenko, C. Schmidt, L. Foucar, N. Kimmel, P. Holl, B. Rudek, B. Erk, A. Hömke, C. Reich, D. Pietschner, G. Weidenspointner, L. Strüder, G. Hauser, H. Gorke, J. Ullrich, I. Schlichting, S. Herrmann, G. Schaller, F. Schopper, H. Soltau, K. Kühnel, R. Andritschke, C. Schröter, F. Krasniqi, M. Bott, S. Schorb, D. Rupp, M. Adolph, T. Gorkhover, H. Hirsemann, G. Potdevin, H. Graafsma, B. Nilsson, H. N. Chapman, and J. Hajdu“Single mimivirus particles intercepted and imaged with an X-ray laser,” Nature 470, 78–81 (2011). [CrossRef] [PubMed]

3.

J. Frank“Single-particle imaging of macromolecules by cryo-electron microscopy,” Annu. Rev. Biophys. Biomolec. Struct. 31, 303–319 (2002). [CrossRef]

4.

N. Fischer, A. L. Konevega, W. Wintermeyer, M. V. Rodnina, and H. Stark“Ribosome dynamics and tRNA movement by time-resolved electron cryomicroscopy,” Nature 466, 329–333 (2010). [CrossRef] [PubMed]

5.

J. B. Tenenbaum, V. de Silva, and J. C. Langford“A global geometric framework for nonlinear dimensionality reduction,” Science 290, 2319–2323 (2000). [CrossRef] [PubMed]

6.

S. T. Roweis and S. K. Saul“Nonlinear dimensionality reduction by locally linear embedding,” Science 290, 2323–2326 (2000). [CrossRef] [PubMed]

7.

M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput. 13, 1373–1396 (2003). [CrossRef]

8.

D. L. Donoho and C. Grimes“Hessian eigenmaps: New locally linear embedding techniques for high-dimensional data,” Proc. Natl. Acad. Sci. U.S.A. 100, 5591–5596 (2003). [CrossRef]

9.

R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. Zucker“Geometric diffusions as a tool for harmonic analysis and structure definition on data,” Proc. Natl. Acad. Sci. U.S.A. 102, 7426–7431 (2005). [CrossRef] [PubMed]

10.

R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [CrossRef]

11.

R. R. Coifman, Y. Shkolnisky, F. J. Sigworth, and A. Singer“Reference free structure determination through eigenvectors of center of mass operators,” Appl. Comput. Harmon. Anal. 28, 296–312 (2010). [CrossRef] [PubMed]

12.

A. L. Ferguson, A. Z. Panagiotopoulos, P. G. Debenedetti, and I. G. Kevrekidis“Systematic determination of order parameters for chain dynamics using diffusion maps,” Proc. Natl. Acad. Sci. U.S.A. 107, 13597–13602 (2010). [CrossRef] [PubMed]

13.

A. Singer, R. R. Coifman, F. J. Sigworth, D. W. Chester, and Y. Shkolnisky“Detecting consistent common lines in cryo-EM by voting,” J. Struct. Biol. 169, 312–322 (2010). [CrossRef]

14.

http://www.youtube.com/watch?v=uat-1voeP3o.

15.

P. Schwander, D. Giannakis, C. H. Yoon, and A. Ourmazd“The symmetries of image formation by scattering. II. Applications,” Opt. Express (2012). (submitted).

16.

R. W. Gerchberg and W. O. Saxton“A practical algorithm for the determination of the phase from image and diffraction plane pictures,” Optik 35, 237–246 (1972).

17.

J. R. Fienup“Reconstruction of an object from the modulus of its Fourier transform,” Opt. Lett. 3, 27–29 (1978). [CrossRef] [PubMed]

18.

F. Oszlányi and A. Süto“Ab initio structure solution by charge flipping,” Acta Crystallogr. 60, 134–141 (2004). [CrossRef]

19.

F. NattererThe Mathematics of Computerized Tomography (SIAM, 2001). [CrossRef]

20.

J. Girard, G. Maire, H. Giovannini, A. Talneau, K. Belkebir, P. C. Chaumet, and A. Sentenac“Nanometric resolution using far-field optical tomographic microscopy in the multiple scattering regime,” Phys. Rev. A 82, 061801(R) (2010). [CrossRef]

21.

A. Sentenac, O. Haeberle, and K. Belkebir“Introduction,” J. Mod. Opt. 57, 685 (2010). [CrossRef]

22.

R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys. 5, 64–67 (2008). [CrossRef]

23.

N. T. D. Loh and V. Elser“Reconstruction algorithm for single-particle diffraction imaging experiments,” Phys. Rev. E 80, 026705–1–026705–20 (2009). [CrossRef]

24.

P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys. 12, 1–15 (2010). [CrossRef]

25.

S. H. W. Scheres, H. Gao, M. Valle, G. T. Herman, P. P. B. Eggermont, J. Frank, and J.-M. Carazo“Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization,” Nat. Methods 4, 27–29 (2007). [CrossRef]

26.

L. Younes, P. W. Michor, J. Shah, and D. Mumford“A metric on shape space with explicit geodesics,” Atti Accad. Naz. Lincei, Cl. Sci. Fis., Mat. Nat., Rend. Lincei, Mat. Appl. 9, 25–57 (2008). [CrossRef]

27.

T. Lin, H. Zha, and S. Lee“Riemannian manifold learning fo rnonlinear dimensionality reduction,” in ECCV Part I, LNCS,, A. Leondardis, H. Bischof, and A. Pinzeds. (Springer-Verlag, 2006), 44–55.

28.

B. Schölkopf, B. Smola, and K.-R. Müller“Nonlinear component analysis as an kernel eigenvalue problem,” Neural Comput. 10, 1299–1319 (1998). [CrossRef]

29.

C. M. Bishop, M. Svensen, and C. K. I. Williams“GTM: The generative topographic mapping,” Neural Comput. 463, 379–383 (1998).

30.

B. Moths and A. Ourmazd“Bayesian algorithms for recovering structure from single-particle diffraction snapshots of unknown orientation: a comparison,” Acta Crystallogr. A67 (2011).

31.

M. Balasubramanian and E. L. Schwartz“The Isomap algorithm and topological stability,” Science 295, 5552 (2002). [CrossRef]

32.

R. Coifman, Y. Shkolnisky, F. Sigworth, and A. Singer“Graph Laplacian tomography from unknown random projections,” IEEE Trans. Image Process. 17, 1891–1899 (2008). [CrossRef] [PubMed]

33.

B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).

34.

S. LangIntroduction to Differentiable Manifolds (Springer-Verlag, 2002).

35.

E. P. WignerGroup Theory and its Application to the Quantum Mechanics of Atomic Spectra (Academic Press, 1959).

36.

L. C. Biedenharn and J. D. LouckAngular Momentum in Quantum Physics (Addison Wesley, 1981).

37.

G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]

38.

B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D 8, 1048–1060 (1973). [CrossRef]

39.

A. H. Taub“Empty space-times admitting a three parameter group of motions,” Ann. Math. 53, 472–490 (1951). [CrossRef]

40.

J. M. CowleyDiffraction Physics, 3rd ed. (North Holland, 1995).

41.

A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).

42.

J. B. KuipersQuaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality (Princeton University Press, 2002). [PubMed]

43.

S. LangFundamentals of Differential Geometry (Springer-Verlag, 1998).

44.

A. M. Bronstein, M. M. Bronstein, and R. KimmelNumerical Geometry of Non-Rigid Shapes (Springer, 2007).

45.

T. Sauer, J. A. Yorke, and M. Casdagli“Embedology,” J. Stat. Phys. 65, 579–616 (1991). [CrossRef]

46.

R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).

47.

P. H. BérardSpectral Geometry: Direct and Inverse Problems, (Springer-Verlag, 1989).

48.

S. RosenbergThe Laplacian on a Riemannian Manifold (Cambridge University Press, 1997). [CrossRef]

49.

N. J. VilenkinSpecial Functions and the Theory of Group Representations, (American Mathematical Society, 1968).

50.

D. A. Varshalovich, A. N. Moskalev, and V. K. KhersonskiiQuantum Theory of Angular Momentum (World Scientific, 1988).

51.

J. L. McCauleyClassical Mechanics: Transformations, Flows, Integrable and Chaotic Dynamics (Cambridge University Press, 1997).

52.

C. Misner“Mixmaster universe,” Phy. Rev. Lett. 22, 1071–1074 (1969). [CrossRef]

53.

S. Lafon“Diffusion maps and geometric harmonics,” Ph.D. thesis, Yale University (2004).

54.

W. D. RossPlato’s Theory of Ideas (Oxford University Press, 1951). [PubMed]

55.

K. Belkebir and M. Saillard“Testing inversion algorithms against experimental data: Inhomogeneous targets,” Inverse Probl. 21, S1 (2004). [CrossRef]

56.

J. M. Geffrin and P. Sabouroux“Continuing with the Fresnel database: Experimental setup and improvements in 3D scattering measurements,” Inverse Probl. 25, 024001 (2009). [CrossRef]

57.

Y. LeCun, J. S. Denker, S. Solla, R. E. Howard, and L. D. Jackel“Optimal brain damage,” in Advances in Neural Information Processing Systems (NIPS 1989), D. Touretzkyed. (Morgan Kaufman, 1990), Vol. 2, pp. 598–605.

58.

D. T. Cromer and J. B. Mann“Atomic scattering factors computed from numerical Hartree-Fock wavefunctions,” Acta Cryst. A 24, 321–324 (1968). [CrossRef]

59.

L. Lovisolo and E. A. B. da Silva“Uniform distribution of points on a hyper-sphere with applications to vector bit-plane encoding,” IEE Proc. Vision Image Signal Process. 148, 187–193 (2001). [CrossRef]

60.

P. Schwander“Efficient interpolation of scattering data to an arbitrary grid,” (in preparation, 2012).

61.

S. Marchesini“Ab initio compressive phase retrieval,” presented at the XXI IUCr Congress, Osaka, Japan, 23–31 Aug. 2008.

62.

P. Bérard, G. Besson, and S. Gallot“Embedding Riemannian manifolds by their heat kernel,” Geom. Funct. Anal. 4, 373–398 (1994). [CrossRef]

63.

G. W. Stewart“Error and perturbation bounds for subspaces associated with certain eigenvalue problems,” SIAM Rev. 15, 727–764 (1973). [CrossRef]

64.

H.-D. Cao and X.-P. Zhu“Hamilton-Perelman’s proof of the Poincaré conjecture and the geometrization conjecture,” (2006). arxiv:math/0612069v1 [math.DG].

65.

P. ToppingLecture Notes on Ricci Flow (Cambridge University Press, 2006). [CrossRef]

66.

J. F. M. Svensen“GTM: The generative topographic mapping,” Ph.D. thesis, Aston University (1998).

67.

V. L. Shneerson, A. Ourmazd, and D. K. Saldin“Crystallography without crystals. I. the common-line method for assembling a 3D diffraction volume from single-particle scattering,” Acta Cryst. A 64, 303–315 (2008). [CrossRef]

68.

W. HeisenbergDer Teil und das Ganze (R. Piper & Co.Verlag, 1981).

69.

D. Saldin, V. L. Shneerson, R. Fung, and A. Ourmazd“Structure of isolated biomolecules obtained from ultrashort X-ray pulses: Exploiting the symmetry of random orientations,” J. Phys.: Condens. Matter 21, 134014 (2009). [CrossRef]

70.

P. Kostelec and D. Rockmore“FFTs on the rotation group,” Santa Fe Institute working paper #03-11-060 (2003).

OCIS Codes
(140.2600) Lasers and laser optics : Free-electron lasers (FELs)
(180.6900) Microscopy : Three-dimensional microscopy
(290.3200) Scattering : Inverse scattering
(290.5840) Scattering : Scattering, molecules
(290.5825) Scattering : Scattering theory

ToC Category:
Scattering

History
Original Manuscript: February 9, 2012
Revised Manuscript: May 11, 2012
Manuscript Accepted: May 16, 2012
Published: May 23, 2012

Citation
Dimitrios Giannakis, Peter Schwander, and Abbas Ourmazd, "The symmetries of image formation by scattering. I. Theoretical framework," Opt. Express 20, 12799-12826 (2012)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-20-12-12799


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. W. A. Freiwald and D. Y. Tsao“Functional compartmentalization and viewpoint generalization within the macaque face-processing system,” Science330, 845–851 (2010). [CrossRef] [PubMed]
  2. M. Seibert, T. Ekeberg, F. R. N. C. Maia, M. Svenda, J. Andreasson, O. Jönsson, D. Odić, B. Iwan, A. Rocker, D. Westphal, M. Hantke, D. P. DePonte, A. Barty, J. Schulz, L. Gumprecht, N. Coppola, A. Aquila, M. Liang, T. A. White, A. Martin, C. Caleman, S. Stern, C. Abergel, V. Seltzer, J. Claverie, C. Bostedt, J. D. Bozek, S. Boutet, A. A. Miahnahri, M. Messerschmidt, J. Krzywinski, G. Williams, K. O. Hodgson, M. J. Bogan, C. Y. Hampton, R. G. Sierra, D. Starodub, I. Andersson, S. Bajt, M. Barthelmess, J. C. H. Spence, P. Fromme, U. Weierstall, R. Kirian, M. Hunter, R. B. Doak, S. Marchesini, S. P. Hau-Riege, M. Frank, R. L. Shoeman, L. Lomb, S. W. Epp, R. Hartmann, D. Rolles, A. Rudenko, C. Schmidt, L. Foucar, N. Kimmel, P. Holl, B. Rudek, B. Erk, A. Hömke, C. Reich, D. Pietschner, G. Weidenspointner, L. Strüder, G. Hauser, H. Gorke, J. Ullrich, I. Schlichting, S. Herrmann, G. Schaller, F. Schopper, H. Soltau, K. Kühnel, R. Andritschke, C. Schröter, F. Krasniqi, M. Bott, S. Schorb, D. Rupp, M. Adolph, T. Gorkhover, H. Hirsemann, G. Potdevin, H. Graafsma, B. Nilsson, H. N. Chapman, and J. Hajdu“Single mimivirus particles intercepted and imaged with an X-ray laser,” Nature470, 78–81 (2011). [CrossRef] [PubMed]
  3. J. Frank“Single-particle imaging of macromolecules by cryo-electron microscopy,” Annu. Rev. Biophys. Biomolec. Struct.31, 303–319 (2002). [CrossRef]
  4. N. Fischer, A. L. Konevega, W. Wintermeyer, M. V. Rodnina, and H. Stark“Ribosome dynamics and tRNA movement by time-resolved electron cryomicroscopy,” Nature466, 329–333 (2010). [CrossRef] [PubMed]
  5. J. B. Tenenbaum, V. de Silva, and J. C. Langford“A global geometric framework for nonlinear dimensionality reduction,” Science290, 2319–2323 (2000). [CrossRef] [PubMed]
  6. S. T. Roweis and S. K. Saul“Nonlinear dimensionality reduction by locally linear embedding,” Science290, 2323–2326 (2000). [CrossRef] [PubMed]
  7. M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput.13, 1373–1396 (2003). [CrossRef]
  8. D. L. Donoho and C. Grimes“Hessian eigenmaps: New locally linear embedding techniques for high-dimensional data,” Proc. Natl. Acad. Sci. U.S.A.100, 5591–5596 (2003). [CrossRef]
  9. R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. Zucker“Geometric diffusions as a tool for harmonic analysis and structure definition on data,” Proc. Natl. Acad. Sci. U.S.A.102, 7426–7431 (2005). [CrossRef] [PubMed]
  10. R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal.21, 5–30 (2006). [CrossRef]
  11. R. R. Coifman, Y. Shkolnisky, F. J. Sigworth, and A. Singer“Reference free structure determination through eigenvectors of center of mass operators,” Appl. Comput. Harmon. Anal.28, 296–312 (2010). [CrossRef] [PubMed]
  12. A. L. Ferguson, A. Z. Panagiotopoulos, P. G. Debenedetti, and I. G. Kevrekidis“Systematic determination of order parameters for chain dynamics using diffusion maps,” Proc. Natl. Acad. Sci. U.S.A.107, 13597–13602 (2010). [CrossRef] [PubMed]
  13. A. Singer, R. R. Coifman, F. J. Sigworth, D. W. Chester, and Y. Shkolnisky“Detecting consistent common lines in cryo-EM by voting,” J. Struct. Biol.169, 312–322 (2010). [CrossRef]
  14. http://www.youtube.com/watch?v=uat-1voeP3o .
  15. P. Schwander, D. Giannakis, C. H. Yoon, and A. Ourmazd“The symmetries of image formation by scattering. II. Applications,” Opt. Express (2012). (submitted).
  16. R. W. Gerchberg and W. O. Saxton“A practical algorithm for the determination of the phase from image and diffraction plane pictures,” Optik35, 237–246 (1972).
  17. J. R. Fienup“Reconstruction of an object from the modulus of its Fourier transform,” Opt. Lett.3, 27–29 (1978). [CrossRef] [PubMed]
  18. F. Oszlányi and A. Süto“Ab initio structure solution by charge flipping,” Acta Crystallogr.60, 134–141 (2004). [CrossRef]
  19. F. NattererThe Mathematics of Computerized Tomography (SIAM, 2001). [CrossRef]
  20. J. Girard, G. Maire, H. Giovannini, A. Talneau, K. Belkebir, P. C. Chaumet, and A. Sentenac“Nanometric resolution using far-field optical tomographic microscopy in the multiple scattering regime,” Phys. Rev. A82, 061801(R) (2010). [CrossRef]
  21. A. Sentenac, O. Haeberle, and K. Belkebir“Introduction,” J. Mod. Opt.57, 685 (2010). [CrossRef]
  22. R. Fung, V. Shneerson, D. K. Saldin, and A. Ourmazd“Structure from fleeting illumination of faint spinning objects in flight,” Nat. Phys.5, 64–67 (2008). [CrossRef]
  23. N. T. D. Loh and V. Elser“Reconstruction algorithm for single-particle diffraction imaging experiments,” Phys. Rev. E80, 026705–1–026705–20 (2009). [CrossRef]
  24. P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys.12, 1–15 (2010). [CrossRef]
  25. S. H. W. Scheres, H. Gao, M. Valle, G. T. Herman, P. P. B. Eggermont, J. Frank, and J.-M. Carazo“Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization,” Nat. Methods4, 27–29 (2007). [CrossRef]
  26. L. Younes, P. W. Michor, J. Shah, and D. Mumford“A metric on shape space with explicit geodesics,” Atti Accad. Naz. Lincei, Cl. Sci. Fis., Mat. Nat., Rend. Lincei, Mat. Appl.9, 25–57 (2008). [CrossRef]
  27. T. Lin, H. Zha, and S. Lee“Riemannian manifold learning fo rnonlinear dimensionality reduction,” in ECCV Part I, LNCS,, A. Leondardis, H. Bischof, and A. Pinzeds. (Springer-Verlag, 2006), 44–55.
  28. B. Schölkopf, B. Smola, and K.-R. Müller“Nonlinear component analysis as an kernel eigenvalue problem,” Neural Comput.10, 1299–1319 (1998). [CrossRef]
  29. C. M. Bishop, M. Svensen, and C. K. I. Williams“GTM: The generative topographic mapping,” Neural Comput.463, 379–383 (1998).
  30. B. Moths and A. Ourmazd“Bayesian algorithms for recovering structure from single-particle diffraction snapshots of unknown orientation: a comparison,” Acta Crystallogr.A67 (2011).
  31. M. Balasubramanian and E. L. Schwartz“The Isomap algorithm and topological stability,” Science295, 5552 (2002). [CrossRef]
  32. R. Coifman, Y. Shkolnisky, F. Sigworth, and A. Singer“Graph Laplacian tomography from unknown random projections,” IEEE Trans. Image Process.17, 1891–1899 (2008). [CrossRef] [PubMed]
  33. B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).
  34. S. LangIntroduction to Differentiable Manifolds (Springer-Verlag, 2002).
  35. E. P. WignerGroup Theory and its Application to the Quantum Mechanics of Atomic Spectra (Academic Press, 1959).
  36. L. C. Biedenharn and J. D. LouckAngular Momentum in Quantum Physics (Addison Wesley, 1981).
  37. G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]
  38. B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D8, 1048–1060 (1973). [CrossRef]
  39. A. H. Taub“Empty space-times admitting a three parameter group of motions,” Ann. Math.53, 472–490 (1951). [CrossRef]
  40. J. M. CowleyDiffraction Physics, 3rd ed. (North Holland, 1995).
  41. A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).
  42. J. B. KuipersQuaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality (Princeton University Press, 2002). [PubMed]
  43. S. LangFundamentals of Differential Geometry (Springer-Verlag, 1998).
  44. A. M. Bronstein, M. M. Bronstein, and R. KimmelNumerical Geometry of Non-Rigid Shapes (Springer, 2007).
  45. T. Sauer, J. A. Yorke, and M. Casdagli“Embedology,” J. Stat. Phys.65, 579–616 (1991). [CrossRef]
  46. R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).
  47. P. H. BérardSpectral Geometry: Direct and Inverse Problems, (Springer-Verlag, 1989).
  48. S. RosenbergThe Laplacian on a Riemannian Manifold (Cambridge University Press, 1997). [CrossRef]
  49. N. J. VilenkinSpecial Functions and the Theory of Group Representations, (American Mathematical Society, 1968).
  50. D. A. Varshalovich, A. N. Moskalev, and V. K. KhersonskiiQuantum Theory of Angular Momentum (World Scientific, 1988).
  51. J. L. McCauleyClassical Mechanics: Transformations, Flows, Integrable and Chaotic Dynamics (Cambridge University Press, 1997).
  52. C. Misner“Mixmaster universe,” Phy. Rev. Lett.22, 1071–1074 (1969). [CrossRef]
  53. S. Lafon“Diffusion maps and geometric harmonics,” Ph.D. thesis, Yale University (2004).
  54. W. D. RossPlato’s Theory of Ideas (Oxford University Press, 1951). [PubMed]
  55. K. Belkebir and M. Saillard“Testing inversion algorithms against experimental data: Inhomogeneous targets,” Inverse Probl.21, S1 (2004). [CrossRef]
  56. J. M. Geffrin and P. Sabouroux“Continuing with the Fresnel database: Experimental setup and improvements in 3D scattering measurements,” Inverse Probl.25, 024001 (2009). [CrossRef]
  57. Y. LeCun, J. S. Denker, S. Solla, R. E. Howard, and L. D. Jackel“Optimal brain damage,” in Advances in Neural Information Processing Systems (NIPS 1989), D. Touretzkyed. (Morgan Kaufman, 1990), Vol. 2, pp. 598–605.
  58. D. T. Cromer and J. B. Mann“Atomic scattering factors computed from numerical Hartree-Fock wavefunctions,” Acta Cryst. A24, 321–324 (1968). [CrossRef]
  59. L. Lovisolo and E. A. B. da Silva“Uniform distribution of points on a hyper-sphere with applications to vector bit-plane encoding,” IEE Proc. Vision Image Signal Process.148, 187–193 (2001). [CrossRef]
  60. P. Schwander“Efficient interpolation of scattering data to an arbitrary grid,” (in preparation, 2012).
  61. S. Marchesini“Ab initio compressive phase retrieval,” presented at the XXI IUCr Congress, Osaka, Japan, 23–31 Aug. 2008.
  62. P. Bérard, G. Besson, and S. Gallot“Embedding Riemannian manifolds by their heat kernel,” Geom. Funct. Anal.4, 373–398 (1994). [CrossRef]
  63. G. W. Stewart“Error and perturbation bounds for subspaces associated with certain eigenvalue problems,” SIAM Rev.15, 727–764 (1973). [CrossRef]
  64. H.-D. Cao and X.-P. Zhu“Hamilton-Perelman’s proof of the Poincaré conjecture and the geometrization conjecture,” (2006). arxiv:math/0612069v1 [math.DG].
  65. P. ToppingLecture Notes on Ricci Flow (Cambridge University Press, 2006). [CrossRef]
  66. J. F. M. Svensen“GTM: The generative topographic mapping,” Ph.D. thesis, Aston University (1998).
  67. V. L. Shneerson, A. Ourmazd, and D. K. Saldin“Crystallography without crystals. I. the common-line method for assembling a 3D diffraction volume from single-particle scattering,” Acta Cryst. A64, 303–315 (2008). [CrossRef]
  68. W. HeisenbergDer Teil und das Ganze (R. Piper & Co.Verlag, 1981).
  69. D. Saldin, V. L. Shneerson, R. Fung, and A. Ourmazd“Structure of isolated biomolecules obtained from ultrashort X-ray pulses: Exploiting the symmetry of random orientations,” J. Phys.: Condens. Matter21, 134014 (2009). [CrossRef]
  70. P. Kostelec and D. Rockmore“FFTs on the rotation group,” Santa Fe Institute working paper #03-11-060 (2003).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig. 1 Fig. 2 Fig. 3
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited