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

doi:10.1364/OE.20.012799

« 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)

Journal Search
Article Lookup

Article Tools

Citations

Alert me when this article is cited
Export Citation/Save

Full Text
Article Info
References (70)
Cited By
Figures (3)
Metrics

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.

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

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

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

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]

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

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

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

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]

]. 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

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.

After a brief conceptual outline in Sec. 2, we summarize relevant previous work in Sec. 3. The symmetry-based scheme for analyzing scattering data is developed in Sec. 4, and the utility of these concepts demonstrated in Sec. 5 in the context of simulated images from X-ray scattering. We present our conclusions in Sec. 6. Material of a more technical nature, including mathematical derivations and algorithms, is provided in Appendices A and B. A movie of a reconstructed object in 3D is presented as online material [14

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

]. Further applications are described in a subsequent paper [15

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

], hereafter referred to as Paper II.

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.

This perspective naturally leads one to use the tools of differential geometry for data analysis, with the metric playing a particularly important role. In non-technical terms, one would like to relate infinitesimal changes in a given snapshot to the corresponding infinitesimal changes in orientation giving rise to the changes in the snapshot. In other words, one would like to relate the metric of the data manifold produced by the collection of snapshots to the metric of the manifold of rotations. This would allow one to determine the rotation operation connecting any pair of snapshots. The problem, however, is that the metric of scattering manifolds is not simply related to that of the rotation operations. We solve this problem in two steps. First, we show that the metric of the data manifold can be decomposed into two parts, one with high symmetry, and an object-specific “residual” with low symmetry. Second, using results from Lie group theory, we show that the eigenfunctions of the high-symmetry part are directly related to those of the manifold of rotations. This allows one to deduce the snapshot orientations from the high-symmetry part, which is the same for all objects, and use the object-specific part as a fingerprint of each object.

We conclude this section with four observations. First, real datasets necessarily contain a finite number of observations. As such, they must be treated by graph-theoretic means, which tend to the differential geometric limit under appropriate conditions. This issue is addressed below, as needed. Second, we have not distinguished between image and diffraction snapshots. If the dataset consists of the latter, each snapshot, or a reconstructed 3D diffraction volume must be inverted by so-called phasing algorithms [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).

–18

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

]. As this procedure is well established, we do not address it further. Third, the discussion is restricted to the effect of operations on objects with no symmetry. The case where the object itself has specific symmetries will be treated elsewhere. Finally, the knowledge gained in the course of our analysis is sufficient to navigate from any starting point to any desired destination on the manifold; i.e., given any snapshot, produce any other as required. This is, of course, tantamount to possessing a 3D model of the object. As this approach is somewhat unfamiliar, we provide actual 3D models to demonstrate the power of our approach.

3. Previous work

In order to place our work in context, we present a brief summary of previous work. As a review is beyond the scope this paper, the summary is necessarily brief, leaving out much excellent work in this general area.

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

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

–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

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

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

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⁻² 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

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

, 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]

] and/or evolving systems [4

, 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

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

R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5–30 (2006). [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.

]. 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

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

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

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

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

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

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

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

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

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]

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

], 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

], 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

, 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

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]

]. 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

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

, 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

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

–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

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

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

,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

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

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

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 q₁ = Qz (we set Q > 0 by convention) is scattered by an object of density ρ(u) with Patterson function P(u) = ∫ du′ ρ(u′)ρ(u − u′) = P(−u), where u and u′ are position vectors in ℝ³. 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 (\vec{r}) = {[ω (\vec{r}) \int d u P (u) exp (i u \cdot q (\vec{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

\begin{matrix} q (r) = q_{2} (\vec{r}) - q_{1}, \\ q_{2} (\vec{r}) = Q (sin θ cos ϕ, sin θ sin ϕ, cos ϕ), \end{matrix}

(2)

where q₂(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 |ℱ(ρ)|². As a result, no modulus sign is needed in Eq. (1), and a²(r⃗_j) is equal to the intensity I_j at pixel j in Fig. 1.

Fig. 2 Geometry of image formation by scattering. q₁ and q₂ 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 P_R(u) = P(R⁻¹u), where R is a 3 × 3 right-handed rotation matrix; i.e., R^TR = 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

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

,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

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

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, L²(ℝ²). This is a Hilbert space of scalar functions f_i equipped with the usual inner product

(f_{1}, f_{2}) = \int d \vec{r} f_{1} (\vec{r}) f_{2} (\vec{r}),

(3)

and corresponding norm

‖ f_{i} ‖ = {(f_{i}, f_{i})}^{1 / 2} .

(4)

In many respects, L²(ℝ²) can be though of as a generalization of Euclidean space to infinite dimensions. In particular, the L² norm induces a distance ‖f₁ − f₂‖ analogous to the standard distance in finite-dimensional Euclidean space. Moreover, viewed as a manifold [43

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

], L²(ℝ²) 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 L²(ℝ²), or manifolds embedded in L²(ℝ²).

We describe the image formation process as an embedding [33

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

,34

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

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

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

, 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

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 L²(ℝ²) in Eq. (3) to an equivalent inner product between tangent vectors on the data manifold. Specifically, given tangent vectors v₁ and v₂ on 𝒮, the induced metric g is defined through the action

g (v_{1}, v_{2}) = (Φ^{*} (v_{1}), Φ^{*} (v_{2})),

(5)

where Φ^* is the so-called derivative map associated with Φ [43

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

, 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 = \sum_{μ, ν = 1}^{3} g_{μ ν} E^{μ} E^{ν},

(6)

where {E¹, E², E³} is a basis of dual vector fields on 𝒮. Note that ds² = g(δv, δv) corresponds to the squared distance between two nearby points on 𝒮 with relative separation δv. The integral of ds² 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

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

, 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) = - \int d \vec{r} ω (\vec{r}) \nabla \cdot [J_{μ} q a_{R} (q)] \nabla \cdot [J_{ν} q a_{R} (q)] |_{q (\vec{r})} .

(7)

In the above, ∫ dr⃗ denotes integration over the detector plane; q(r⃗) is the change in wavevector given by Eq. (2); ∇ = (∂/∂q_x, ∂/∂q_y, ∂/∂q_z) 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, a_R 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

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

, 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

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

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.

As discussed in more detail below, the isometry group of g in Eq. (5) is generally not large-enough to induce a transitive action; i.e., there exist points on the manifold that cannot be mapped to one another through an isometry. Nevertheless, considerable progress in the interpretation of datasets produced by scattering can be made by establishing the existence of a related metric h, whose isometry group meets the conditions for transitivity. As shown below, the properties of h can be used to interpret the results of data analysis performed on (𝒮,g). By combining aspects of group theory and differential geometry, the general techniques developed here constitute a novel approach for analyzing scattering data, and potentially other machine-learning applications.

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

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

, 41

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

, 46

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

]. These maps, respectively denoted L_Q and R_Q, 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,

\begin{matrix} L_{Q} (R) = QR, & R_{Q} (R) = RQ . \end{matrix}

(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 L_Q or R_Q (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

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

, 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, {sin}^{2} χ, {sin}^{2} χ {sin}^{2} θ),

(9)

which is identical to the canonical metric on the three-sphere S³. 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

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]

], defined as

Δ_{B} (f) = - {| B |}^{- 1 / 2} \sum_{μ, ν = 1}^{m} \partial_{μ} ({| B |}^{1 / 2} B^{μ ν} \partial_{ν} f)

(10)

for |B| = det[B_μν], [B^μν] = [B_μν]⁻¹, 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

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

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).

], complex-valued functions on SO(3), which solve the eigenvalue problem

Δ_{B} D_{m m^{'}}^{j} (R) = j (j + 1) D_{m m^{'}}^{j} (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, (α¹, α², α³), explicit formulas for the j = 1 D-functions are

\begin{array}{l} D_{00}^{1} (α^{1}, α^{2}, α^{3}) = cos α^{2}, \\ D_{\pm 10}^{1} (α^{1}, α^{2}, α^{3}) = - e^{\mp i α^{1}} sin (α^{2}) / 2^{1 / 2}, \\ D_{0, \pm 1}^{1} (α^{1}, α^{2}, α^{3}) = - e^{\mp i α^{3}} sin (α^{2}) / 2^{1 / 2}, \\ D_{11}^{1} (α^{1}, α^{2}, α^{3}) = e^{- i (α^{1} + α^{3})} {cos}^{2} (α^{2} / 2), \\ D_{- 1 - 1}^{1} (α^{1}, α^{2}, α^{3}) = e^{i (α^{1} + α^{3})} {cos}^{2} (α^{2} / 2), \\ D_{- 11}^{1} (α^{1}, α^{2}, α^{3}) = e^{i (α^{1} - α^{3})} {sin}^{2} (α^{2} / 2), \\ D_{1 - 1}^{1} (α^{1}, α^{2}, α^{3}) = e^{- i (α^{1} - α^{3})} {sin}^{2} (α^{2} / 2) . \end{array}

(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 c_pqmm_′ such that

R_{p q} = \sum_{m, m^{'} = - 1}^{1} c_{p q m m^{'}} D_{m m^{'}}^{1} (R),

(13)

where R_pq are the elements of R. Thus, if eigenfunctions of Δ_B could be accessed by processing the observed snapshots a_R on the data manifold, e.g., through one of the graph-theoretic algorithms developed in machine learning [7

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

, 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 = ℓ_{1} E^{1} E^{1} + ℓ_{2} E^{2} E^{2} + ℓ_{3} E^{3} E^{3},

(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

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

,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

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]

,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

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., ℓ₁ = ℓ₂), h describes the motion of an axisymmetric rotor, or the spatial structure of the Taub solution in general relativity [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

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 (

λ_{m}^{j}

y_{m}^{j}

) of Δ_h can be expressed as linear combinations of Wigner D-functions with the same j and m quantum numbers:

y_{m}^{j} = \sum_{m^{'} = - j}^{j} A_{m m^{'}}^{j} D_{m m^{'}}^{j},

(15)

for some linear expansion coefficients

A_{m m^{'}}^{j}

. For the most general metrics with ℓ₁ ≠ ℓ₂ ≠ ℓ₃, no closed-form expression is available for either

A_{m m^{'}}^{j}

, or the corresponding eigenvalues

λ_{m}^{j}

. However, in the special case of axisymmetric rotors, any

A_{m m^{'}}^{j}

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

y_{m m^{'}}^{j}

) is nine-dimensional. In particular, Eq. (13) can be applied directly with

D_{m m^{'}}^{1}

replaced by

y_{m m^{'}}^{1}

The eigenvalue

λ_{m}^{j}

corresponding to

y_{m m^{'}}^{j}

in the so-called prolate configuration, ℓ₁ = ℓ₂ ≤ ℓ₃, is given by

λ_{m}^{j} = \frac{1}{2 ℓ_{1}} j (j + 1) - (\frac{1}{2 ℓ_{1}} - \frac{1}{2 ℓ_{3}}) m^{2},

(16)

with a similar formula for the oblate configuration ℓ₁ = ℓ₂ ≥ ℓ₃ [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

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

M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput. 13, 1373–1396 (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]

In general, g is not invariant under arbitrary left or right multiplications. The lack of invariance of g under the right multiplication map R_Q can be seen by considering its components in a right-invariant basis. In particular, it can be shown that R_Q 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 a_R with a_QR is then a rotation on the detector plane, which has no influence on the value of the L² 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 ℓ₁ = ℓ₂ (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

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]

]. 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 a_{R_i} in the dataset as a point in nine-dimensional Euclidean space ℝ⁹ with coordinates given by (ψ_i₁,...,ψ_i₉). Here, ψ_ik are eigenvector components of a diffusion operator on a graph constructed from the s observed snapshots (a_R₁,..., a_{R_s}) in n-dimensional data space (see Appendix B). This induces an embedding Ψ of the latent manifold 𝒮 in ℝ⁹ given by

Ψ (R_{i}) = (ψ_{i 1}, \dots, ψ_{i 9}) .

(18)

Provided that the number of observed snapshots is sufficiently large, suitable algorithms (such as Diffusion Map of Coifman and Lafon [10

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

, 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

ψ_{i k} \approx ψ_{k} (R_{i}),

(19)

where ψ_k(R_i) is the k-th eigenfunction of Δ_g, i.e.,

Δ_{g} ψ_{k} = λ_{k} ψ_{k}

(20)

with

Δ_{g} (\cdot) = - {| g |}^{- 1 / 2} \sum_{μ, ν = 1}^{m} \partial_{μ} [{| g |}^{1 / 2} g^{μ ν} \partial_{ν} (\cdot)] .

(21)

Now, we explicitly employ the symmetries of the homogeneous metric h in Eq. (14), motivated by the decomposition of g in Eq. (17), as follows. Express each eigenfunction of the homogeneous Laplacian Δ_h with j = 1 as a linear combination of the eigenfunctions ψ_k of the inhomogeneous Laplacian, viz.,

D_{m m^{'}}^{1} = \sum_{k} c_{m m^{'} k} ψ_{k},

(22)

where we have made use of the correspondence in Eq. (15) between Wigner D-functions and the eigenfunctions associated with the axisymmetric rotor. These eigenfunctions are related to the matrix elements of the rotation operators R_i, in accordance with Eq. (13). Retaining only the first nine ψ_k, determine the elements of the rotation matrix by a least-squares fit [Eqs. (62)] of the coordinates computed in Eq. (19) via graph-theoretic analysis.

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 R_i 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

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

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 q₁ ≠ q₂, 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

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]

], 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

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 10⁴× more complex than previously attempted [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]

]. 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

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

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π²(D/d)³ ≈ 8.5 × 10⁵, where D = 54 Å is the diameter of the molecule [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 × 10⁶ 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 × 10⁴; number of datapoints for least-squares fitting r = 8 × 10⁴. 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,

ɛ = {[\frac{1}{s (s - 1)} \sum_{i \neq j} {({\tilde{D}}_{i j} - D_{i j})}^{2}]}^{1 / 2} .

(23)

In the above, D_ij = 2 arccos(|τ_i ·τ_j|) and D̃_ij = 2 arccos(|τ̃_i ·τ̃_j|) are respectively the true and estimated internal distances between orientations R_i and R_j, 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

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

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

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

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

Fig. 3 Three-dimensional electron density of the closed conformation of E. coli adenylate kinase, recovered from 2×10⁶ 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

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

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

y_{m}^{j}

of Eq. (15) associated with some axisymmetric rotor metric h [Eq. (14) with ℓ₁ = ℓ₂]. This is a significantly weaker condition than requiring that the metrics themselves be close, or, equivalently, that a suitably-defined norm ‖w‖_h 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

\frac{1}{Λ_{-}^{2}} h (v, v) \leq g (v, v) \leq Λ_{+}^{2} h (v, v),

(24)

for all tangent vectors v and points on the data manifold [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 ℓ = ℓ₁/ℓ₃ 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) ‖h‖_h = 1 by construction; and (2) ‖w‖_h is bounded from below through the upper Lipschitz constant:

{‖ w ‖}_{h} \geq Λ_{+} - 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_μν (R_i)]^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 ‖w‖_h 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 V_g spanned by the leading nine eigenvectors ψ₁,...,ψ₉ determined through graph-theoretic analysis and the corresponding space V_h spanned by the leading nine eigenfunctions of the Laplace-Beltrami operator Δ_h associated with the axisymmetric rotor metric h, evaluated at the known orientations R_i. A standard measure of that distance from linear algebra is [63

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

]

γ = {‖ Π_{g} - Π_{h} ‖}_{2},

(26)

where Π_g and Π_h are orthogonal projectors from ℝ^s (the space spanned by all eigenfunctions of a data set with s samples) to V_g and V_h, respectively, and ‖·‖₂ denotes the spectral norm of matrices (recall that ‖A‖₂ 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 V_g from V_h. For the ADK and chignolin data sets, the eigenvectors computed via the Diffusion Map algorithm [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 ‖w‖_h). 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

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]

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

C \propto R^{8} = {(D / d)}^{8},

(27)

with D the object diameter and d the spatial resolution [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

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

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

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

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

, 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

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

\begin{array}{l} K = \frac{8 π^{2}}{S} {(\frac{D}{d})}^{3}, \\ s = f K = \frac{8 π^{2} f}{S} {(\frac{D}{d})}^{2}, \\ n = {\frac{4 D}{λ} tan [2 arcsin (\frac{λ}{2 d})]}^{2} \approx 16 {(\frac{D}{d})}^{2}, \end{array}

(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

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

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

C \propto M_{rot} s N_{photons},

(29)

where M_rot is the number of rotation samples (orientational bins), and that this leads to an R⁶ 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 N_photons; (2) N_photons 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

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 N_photons. Note that M_rot 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

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 D³. Thus,

\begin{array}{r} M_{rot} = \frac{8 π^{2}}{S} {(\frac{D}{d})}^{3}, \\ s = \frac{8 π^{2} f}{S} {(\frac{D}{d})}^{2}, \\ N_{photons} \sim n = 16 {(\frac{D}{d})}^{2}, \end{array}

(30)

leading to the same R⁸ 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 (D_chig = 16 Å, d_chig = 1.8 Å), to ADK (D_ADK = 54 Å, D_{ADK (support)} = 72 Å, d_ADK = 2.45 Å) is

{(\frac{D_{ADK (support)} / d_{ADK}}{D_{chig} / d_{chig}})}^{8} = {(\frac{29.4}{8.9})}^{8} = 1.4 \times 10^{4} .

(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(10³) and O(10⁴) 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 10⁴.

Table 1 Computational complexity of orientational recovery for GroEL and ADK

	GroEL	ADK
	GroEL	Sparse representation	No sparse representation
N_photons	10²	∼ 10³	1.6 × 10⁴
s	10⁶	2 × 10⁶	2 × 10⁶
M_rot	2.5 × 10⁴	2 × 10⁶	2 × 10⁶
M_rot s N_photons	2.5 × 10¹²	4 × 10¹⁵	6.4 × 10¹⁶
Ratio to GroEL	1	1.6 × 10³	2.6 × 10⁴

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 S² [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

We have shown that a Riemannian formulation of scattering reveals underlying, object-independent symmetries, which stem from the nature of operations in 3D space and projection onto a 2D detector. These symmetries lead to identification of the natural eigenfunctions of manifolds produced by data from a wide range of scattering scenarios, and thus to physically-based interpretation of the outcome of graph-theoretic analysis of such data. In practical terms, the ability to access the leading eigenfunctions of the homogeneous metric offers a computationally efficient route to determining object orientation without object recognition, while the object-dependent term provides a concise fingerprint of the object for recognition purposes. There are tantalizing indications that face perception in higher primates may occur in this way [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]

]. The ability to use symmetries to navigate on the data manifold is tantamount to efficient machine learning in 3D, in the sense that given any 2D projection, any other can be reconstructed.

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

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

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

Appendices

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 L²(ℝ²) 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

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

, 34

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

, 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 a_R = Φ(R), that transformation is given by

{\tilde{ϕ}}_{α} (a_{R}) = a_{R_{α}}

(33)

with a_{R_α} 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_{α \to 0} \frac{a_{R_{α}} - a_{R}}{α} .

(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

\begin{matrix} L_{α}^{μ} (R) = exp (α J_{μ}) R & for & μ \in {1, 2, 3}, \end{matrix}

(35)

where α is the rotation angle in radians, and J₁, J₂, and J₃ are 3 × 3 antisymmetric matrices generating rotations about the x, y, and z axes:

\begin{matrix} J_{1} = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & - 1 \\ 0 & 1 & 0 \end{matrix}), & J_{2} = (\begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ - 1 & 0 & 0 \end{matrix}), & J_{3} = (\begin{matrix} 0 & - 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) . \end{matrix}

(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_{μ}) (\vec{r}) = {[ω (\vec{r})]}^{1 / 2} \nabla \cdot [J_{μ} q a_{R} (q)] |_{q = q (\vec{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 {e₁, e₂, e₃} 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 R_Q in Eq. (8) [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

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) = \sum_{j = 0}^{\infty} \sum_{m = - j}^{j} a_{j}^{m} (q) Y_{j}^{m} (θ, ϕ),

(40)

where

a_{j}^{m}

are complex functions of the radial coordinate q in reciprocal space, and

Y_{j}^{m}

are spherical harmonics. Note the property

a_{j}^{m *} = {(- 1)}^{m} a_{j}^{- m}

, which is a consequence of a(q) being real. Making use of the standard formula describing rotations of spherical harmonics via Wigner D-matrices,

Y_{j}^{m} (R^{- 1} (θ, ϕ)) = \sum_{m^{'} = - j}^{j} D_{m m^{'}}^{j} (R) Y_{j}^{m^{'}} (θ, ϕ),

(41)

it follows that the amplitude distribution a_R = Φ(R) corresponding to object orientation R is given by

a_{R} (q) = \sum_{j = 0}^{\infty} \sum_{m, m^{'} = - j}^{j} a_{j}^{m^{'}} (q) D_{m m^{'}}^{j} (R) Y_{j}^{m} (θ, ϕ) .

(42)

Inserting the above in Eq. (7) leads to the following general expression for the metric components,

g_{μ ν} (R) = \sum_{j_{1}, j_{2} = 0}^{\infty} \sum_{m_{1}, m_{1}^{'} = - j_{1}}^{j_{1}} \sum_{m_{2}, m_{2}^{'} = - j_{2}}^{j_{2}} {(- 1)}^{m_{1} + m_{1}^{'}} D_{- m_{1}, - m_{1}^{'}}^{j_{1}} (R) D_{m_{2}, m_{2}^{'}}^{j_{2}} (R) K_{μ ν}^{j_{1} m_{1} m_{1}^{'} j_{2} m_{2} m_{2}^{'}},

(43)

In the above,

K_{μ ν}^{j_{1} m_{1} m_{1}^{'} j_{2} m_{2} m_{2}^{'}}

are complex-valued coefficients, which vanish unless the following conditions are met (together with the corresponding conditions obtained by interchanging μ and ν):

\begin{matrix} m_{2} = m_{1} \pm 2 or m_{2} = m_{1} for (μ, ν) = {\begin{matrix} (1, 1), \\ (2, 2), \end{matrix} \\ m_{2} = m_{1} \pm 2 for (μ, ν) = (1, 2), \\ m_{2} = m_{1} \pm 1 for (μ, ν) = {\begin{matrix} (1, 3), \\ (2, 3), \end{matrix} \\ m_{2} = m_{1} for (μ, ν) = (3, 3) . \end{matrix}

(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

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

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

{{\hat{g}}_{μ, ν}^{j}}_{j = 0}^{\infty}

of (2j + 1) × (2j + 1) matrices

g_{μ ν}^{j}

, whose components are given by

{[{\hat{g}}_{μ ν}^{j}]}_{m m^{'}} = \int d V (R) g_{μ ν} (R) D_{m^{'} m}^{j} (R^{- 1}) .

(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

D_{m m^{'}}^{j}

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 (α¹, α², α³) parameterizing a rotation matrix R, is dV (R) = |B|^1/2dα¹ dα² dα³ with |B| = (det[B_μν])^1/2 = sin(α²). The collection of the

{\hat{g}}_{μ ν}^{j}

matrices in Eq. (46) may be used to recover g′(R) via the inverse transform

g_{μ ν} (R) = \frac{1}{8 π^{2}} \sum_{j = 0}^{\infty} (2 j + 1) tr ({\hat{g}}_{μ ν}^{j} D^{j} (R)),

(47)

where

D^{j} (R) = [D_{m m^{'}}^{h} (R)]

is the j-th Wigner matrix of size (2j + 1) ×(2j + 1). Because D⁰ is the trivial representation of SO(3), a constant scalar on the manifold, the term

{\hat{g}}_{μ ν}^{0}

corresponds to the homogeneous part of the metric. The

{\hat{g}}_{μ ν}^{j}

with j ≥ 1 give rise to the inhomogeneous tensor w, which encodes object-specific information. That is, we have

\begin{matrix} h_{μ ν} = {\hat{g}}_{μ ν}^{0}, & w_{μ ν} = \frac{1}{8 π^{2}} \sum_{j = 1}^{\infty} (2 j + 1) tr ({\hat{g}}_{μ ν}^{j} D^{j} (R)) . \end{matrix}

(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

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

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

\begin{array}{l} \int d V (R) D_{m m^{'}}^{j *} (R) D_{m_{1} m_{1}^{'}}^{j_{1}} (R) D_{m_{2} m_{2}^{'}}^{j_{2}} (R) & = {(- 1)}^{m + m^{'}} 8 π^{2} (\begin{array}{l} j_{1} & j_{2} & j \\ m_{1} & m_{2} & - m \end{array}) (\begin{array}{l} j_{1} & j_{2} & j \\ m_{1}^{'} & m_{2}^{'} & - m^{'} \end{array}) . \end{array}

(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

\begin{array}{l} {[{\hat{g}}_{μ ν}^{j}]}_{m m^{'}} = \sum_{j_{1} = 0}^{\infty} \sum_{j_{2} = | j_{1} - j |}^{j_{1} + j} \sum_{m_{1}, m_{1}^{'} = - j_{1}}^{j_{1}} \sum_{m_{2}, m_{2}^{'} = - j_{2}}^{j_{2}} & K_{μ ν}^{j_{1} m_{1} m_{1}^{'} j_{2} m_{2} m_{2}^{'}} \frac{{(- 1)}^{m_{1} + m_{1}^{'} + m + m^{'}}}{16 π^{2}} \\ \times (\begin{array}{l} j_{1} & j_{2} & j \\ - m_{1} & m_{2} & m \end{array}) (\begin{array}{l} j_{1} & j_{2} & j \\ - m_{1}^{'} & m_{2}^{'} & m^{'} \end{array}), \end{array}

(50)

where we have employed the triangle inequality, |j₁ − j₂| ≤ j ≤ j₁ + j₂, 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

{[{\hat{g}}_{μ ν}^{j}]}_{m m^{'}}

is non-vanishing. Specifically, it is possible to show that the matrix elements

{[{\hat{g}}_{μ ν}^{j}]}_{m m^{'}}

are zero unless

\begin{matrix} m \in {0, \pm 2}, for (μ, ν) = (1, 1) or (μ, ν) = (2, 2), \\ m \in {\pm 2}, for (μ, ν) = (1, 2), \\ m \in {\pm 1}, for (μ, ν) = (1, 3) or (μ, ν) = (2, 3), \\ m \in {0}, for (μ, ν) = (3, 3) . \end{matrix}

(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 ℓ₁ and ℓ₂ parameters are, in fact, equal. Thus, the components of the induced metric read

\begin{matrix} g_{μ ν} = h_{μ ν} + w_{μ ν}, & [h_{μ ν}] = (\begin{matrix} ℓ_{1} & 0 & 0 \\ 0 & ℓ_{1} & 0 \\ 0 & 0 & ℓ_{3} \end{matrix}) . \end{matrix}

(52)

By construction, the average of w_μν over the manifold vanishes, i.e.,

\int d V (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) = \sum_{μ, ν = 1}^{3} g_{μ ν} (R) v^{μ} v^{ν}

, subject to the constraint

h (v, v) = \sum_{μ, ν = 1}^{3} h_{μ ν} v^{μ} v^{ν} = 1

. This problem is equivalent to solving for every R a generalized eigenvalue problem

\sum_{ν = 1}^{3} g_{μ ν} (R) v_{k}^{ν} = Λ_{k}^{2} (R) \sum_{ν = 1}^{3} h_{μ ν} v_{k}^{ν}

(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 {R_i}. This provides a lower bound to the true Lipschitz constants.

As general background, Bérard, Besson, and Gallot [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

{y_{i}}_{i = 1}^{K}

of Δ_h, one can associate an orthonormal basis of eigenfunctions

{ψ_{i}}_{i = 1}^{K}

of Δ_g satisfying the bound

{‖ ψ_{i} - y_{i} ‖}_{\infty} \leq η_{i} (Λ),

(55)

where ‖·‖_∞ denotes the supremum norm. This means that if one approximates the set of (possibly degenerate) eigenfunctions of Δ_h with corresponding eigenvalues

λ_{1}^{h}, \dots, λ_{K}^{h}

by the eigenfunctions of Δ_g with corresponding eigenvalues λ₁,...,λ_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 ‖w‖_h 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

{‖ u ‖}_{h} = sup_{R, v} {(\frac{| 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, ‖u‖_h 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 ‖g‖_h = Λ₊ ≥ 1. Next, set u = w = g − h, and compute ‖w‖_h = ‖g − h‖_h. The reverse triangle inequality of norms,

{‖ g - h ‖}_{h} \geq | {‖ g ‖}_{h} - {‖ h ‖}_{h} |,

(57)

used in conjunction with the trivial result ‖h‖_h = 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

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 = {{\underline{a}}_{1}, \dots, {\underline{a}}_{s}},

(58)

where a_i = (a_i₁,..., a_in) are n-dimensional vectors of pixel amplitudes (see Fig. 1). As described in Sec. 4.2, the amplitudes are given by a_ij = a_{R_i} (r⃗_j), where r⃗_j is the position of pixel j in the detector plane, and a_{R_i} = Φ (R_i) is the snapshot associated with orientation R_i.

In Ref. [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

\begin{matrix} P_{ɛ} {\underline{ψ}}_{k} = λ_{k} {\underline{ψ}}_{k}, & {\underline{ψ}}_{k} = {(ψ_{1 k}, \dots, ψ_{s k})}^{T}, \end{matrix}

(59)

then the relation ψ_ik ≈ ψ_k(R_i) holds for large-enough s and small-enough ε, where ψ_k(R_i) is the k-th eigenfunction of Δ_g in Eq. (21) evaluated at element R_i 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 W_ij = 𝒦 (a_i, a_j) via a Gaussian kernel

𝒦 ({\underline{a}}_{i}, {\underline{a}}_{j}) = exp (- {‖ {\underline{a}}_{i} - {\underline{a}}_{j} ‖}^{2} / ɛ)

(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 a_i retains the distances up to its d-th nearest neighbor. Hereafter we denote the index of the j-th nearest neighbor of a_i by N_ij, and the corresponding distance by S_ij = ‖a_i − a_{N_ij}‖. Pseudocode for computing P_ε given the s × d distance and index matrices, S = [S_ij] and N = [N_ij], is listed in Table 2.

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

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

Inputs:

s × d distance matrix S

s × d nearest-neighbor index matrix N

Gaussian width ε

Normalization parameter α

Outputs:

s × s sparse transition probability matrix P

1: Construct an s × s sparse symmetric weight matrix W, such that

W_{i j} = {\begin{array}{l} 1, & if i = j, \\ exp (- S_{i k}^{2} / ɛ), & if j = N_{i k}, \\ W_{j i}, & if W_{i j} \neq 0, \\ 0, & otherwise . \end{array}

2: Evaluate the s × s diagonal matrix Q with nonzero elements

Q_{i i} = \sum_{j = 1}^{s} W_{i j}

3: Form the anisotropic kernel matrix K = Q⁻^α WQ⁻^α.

4: Evaluate the s × s diagonal matrix D with nonzero elements

D_{i i} = \sum_{j = 1}^{s} K_{i j}

5: return P_ε = D⁻¹K

Once the eigenvectors in Eq. (59) have been evaluated, the next step in the orientation-recovery process is to evaluate the linear-combination coefficients needed to convert the nine-dimensional embedding coordinates (ψ_l₁,...,ψ_l₉) in Eq. (18) to elements of an approximate rotation matrix R̃_l. This conversion is performed by the discrete analog of Eq. (13), namely

\begin{matrix} {[{\tilde{R}}_{l}]}_{i j} = \sum_{k = 1}^{9} c_{i j k} ψ_{l k}, & 1 \leq l \leq s . \end{matrix}

(61)

Here the expansion coefficients c_ijk are determined by a least-squares minimization of the error functional

𝒢 ({c_{i j k}}) = \sum_{l = 1}^{r} G_{l}^{2} ({c_{i j k}}),

(62)

G_{l}^{2} ({c_{i j k}}) = {‖ {\tilde{R}}_{l}^{T} {\tilde{R}}_{l} - I ‖}^{2} + {| det ({\tilde{R}}_{l}) - 1 |}^{2},

(62b)

{[{\tilde{R}}_{l}]}_{i j} = \sum_{k = 1}^{9} c_{i j k} ψ_{l k},

(62c)

where

‖ M ‖ = {(\sum_{i, j = 1}^{3} M_{i j}^{2})}^{1 / 2}

denotes the Frobenius norm (the entrywise two-norm) of a 3 × 3 matrix M = [M_ij].

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

\tilde{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 × 10⁶, we use r = 8 × 10⁴ datapoints. We denote the total squared residual of the optimization process by 𝒢^*, where 𝒢^* is equal to 𝒢({c_ijk}) in Eq. (62a), with {c_ijk} 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

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

R n = n,

(65)

where χ is the angle of the rotation represented by R, and n = n_x x + n_y y + n_z z is a unit vector in ℝ³ directed along the corresponding axis of rotation. The unit quaternion τ corresponding to R is given by

τ = (cos (χ / 2), sin (χ / 2) n_{x}, sin (χ / 2) n_{y}, sin (χ / 2) n_{z}) .

(66)

In outline, our orientation-recovery method consists of the following three basic steps:

Use Diffusion Map to compute the first nine non-trivial eigenfunctions ψ₁,...,ψ₉ of the diffusion operator P_ε;
Determine the linear combination coefficients c_ijk to transform the ψ_k eigenvectors to (approximate) rotation matrices by solving the nonlinear least squares problem in Eq. (62);
Use the correspondence in Eq. (61) and polar decomposition [Eq. (63)] to assign a rotation matrix R_l to each observed diffraction pattern, and (optionally) extract the parameters of R_l 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

Inputs:

Noise-free snapshots M = {a₁,..., a_s}

Number of retained nearest neighbors d

Number of datapoints in the least-squares fit, r

Gaussian width ε

Outputs:

Estimated quaternions 𝒯 = {τ₁,...,τ_s}

Nearest-neighbor index matrix N

Least-squares residual 𝒢^*

1: Compute the s × d matrices N and S such that

N_ij = index of j-th nearest neighbor to snapshot a_i,

S_ij = ‖a_i − a_{N_ij}‖.

2: return N

3: Compute the sparse transition probability matrix P using the algorithm in Table 2 with inputs S, N, ε, and α = 1.

4: Solve the sparse eigenvalue problem Pψ_k = λ_kψ_k for 0 ≤ k ≤ 9 and 1 = λ₀ < λ₁ ≤ ··· ≤ λ₉.

5: Solve the nonlinear least-squares problem (62).

6: return 𝒢^*

7: for i = 1,...,s do

8: Compute an approximate SO(3) matrix R̃_i for snapshot a_i via Eq. (61).

9: Project R̃_i to an orthogonal matrix R_i using Eq. (63)

10: Convert R_i to a unit quaternion τ_i via Eqs. (64)–(66).

11: return τ_i

12: end for

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

, 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

We acknowledge valuable discussions with Y. LeCun, B. Moths, G. N. Phillips, Jr., R. Rosner, W. Schröter, and members of the UWM Physics Department. We are indebted to C. H. Yoon for stimulating discussions and comments on an earlier version of the manuscript, and grateful to W. Schröter for pointing out that a link between symmetries and Platonic Forms was also discussed by Werner Heisenberg and Carl Friedrich von Weizsacker in the context of elementary particles. One of us (DG) is grateful to the Random Shapes Program held in 2007 at the Institute for Pure & Applied Mathematics. This work was partially supported by the U.S. Department of Energy Office of Science (SC-22, BES) award #DE-SC0002164 and a UWM Research Growth Initiative award. All authors contributed equally to this work.

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

W. A. Freiwald and D. Y. Tsao“Functional compartmentalization and viewpoint generalization within the macaque face-processing system,” Science330, 845–851 (2010). [CrossRef] [PubMed]
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]
J. Frank“Single-particle imaging of macromolecules by cryo-electron microscopy,” Annu. Rev. Biophys. Biomolec. Struct.31, 303–319 (2002). [CrossRef]
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]
J. B. Tenenbaum, V. de Silva, and J. C. Langford“A global geometric framework for nonlinear dimensionality reduction,” Science290, 2319–2323 (2000). [CrossRef] [PubMed]
S. T. Roweis and S. K. Saul“Nonlinear dimensionality reduction by locally linear embedding,” Science290, 2323–2326 (2000). [CrossRef] [PubMed]
M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput.13, 1373–1396 (2003). [CrossRef]
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]
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]
R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal.21, 5–30 (2006). [CrossRef]
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]
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]
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]
http://www.youtube.com/watch?v=uat-1voeP3o .
P. Schwander, D. Giannakis, C. H. Yoon, and A. Ourmazd“The symmetries of image formation by scattering. II. Applications,” Opt. Express (2012). (submitted).
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).
J. R. Fienup“Reconstruction of an object from the modulus of its Fourier transform,” Opt. Lett.3, 27–29 (1978). [CrossRef] [PubMed]
F. Oszlányi and A. Süto“Ab initio structure solution by charge flipping,” Acta Crystallogr.60, 134–141 (2004). [CrossRef]
F. NattererThe Mathematics of Computerized Tomography (SIAM, 2001). [CrossRef]
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]
A. Sentenac, O. Haeberle, and K. Belkebir“Introduction,” J. Mod. Opt.57, 685 (2010). [CrossRef]
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]
N. T. D. Loh and V. Elser“Reconstruction algorithm for single-particle diffraction imaging experiments,” Phys. Rev. E80, 026705–1–026705–20 (2009). [CrossRef]
P. Schwander, R. Fung, G. N. Phillips, and A. Ourmazd“Mapping the conformations of biological assemblies,” New J. Phys.12, 1–15 (2010). [CrossRef]
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]
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]
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.
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]
C. M. Bishop, M. Svensen, and C. K. I. Williams“GTM: The generative topographic mapping,” Neural Comput.463, 379–383 (1998).
B. Moths and A. Ourmazd“Bayesian algorithms for recovering structure from single-particle diffraction snapshots of unknown orientation: a comparison,” Acta Crystallogr.A67 (2011).
M. Balasubramanian and E. L. Schwartz“The Isomap algorithm and topological stability,” Science295, 5552 (2002). [CrossRef]
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]
B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).
S. LangIntroduction to Differentiable Manifolds (Springer-Verlag, 2002).
E. P. WignerGroup Theory and its Application to the Quantum Mechanics of Atomic Spectra (Academic Press, 1959).
L. C. Biedenharn and J. D. LouckAngular Momentum in Quantum Physics (Addison Wesley, 1981).
G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]
B. L. Hu“Scalar waves in the mixmaster universe. I. The Helmholtz equation in a fixed background,” Phys. Rev. D8, 1048–1060 (1973). [CrossRef]
A. H. Taub“Empty space-times admitting a three parameter group of motions,” Ann. Math.53, 472–490 (1951). [CrossRef]
J. M. CowleyDiffraction Physics, 3rd ed. (North Holland, 1995).
A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).
J. B. KuipersQuaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality (Princeton University Press, 2002). [PubMed]
S. LangFundamentals of Differential Geometry (Springer-Verlag, 1998).
A. M. Bronstein, M. M. Bronstein, and R. KimmelNumerical Geometry of Non-Rigid Shapes (Springer, 2007).
T. Sauer, J. A. Yorke, and M. Casdagli“Embedology,” J. Stat. Phys.65, 579–616 (1991). [CrossRef]
R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).
P. H. BérardSpectral Geometry: Direct and Inverse Problems, (Springer-Verlag, 1989).
S. RosenbergThe Laplacian on a Riemannian Manifold (Cambridge University Press, 1997). [CrossRef]
N. J. VilenkinSpecial Functions and the Theory of Group Representations, (American Mathematical Society, 1968).
D. A. Varshalovich, A. N. Moskalev, and V. K. KhersonskiiQuantum Theory of Angular Momentum (World Scientific, 1988).
J. L. McCauleyClassical Mechanics: Transformations, Flows, Integrable and Chaotic Dynamics (Cambridge University Press, 1997).
C. Misner“Mixmaster universe,” Phy. Rev. Lett.22, 1071–1074 (1969). [CrossRef]
S. Lafon“Diffusion maps and geometric harmonics,” Ph.D. thesis, Yale University (2004).
W. D. RossPlato’s Theory of Ideas (Oxford University Press, 1951). [PubMed]
K. Belkebir and M. Saillard“Testing inversion algorithms against experimental data: Inhomogeneous targets,” Inverse Probl.21, S1 (2004). [CrossRef]
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]
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.
D. T. Cromer and J. B. Mann“Atomic scattering factors computed from numerical Hartree-Fock wavefunctions,” Acta Cryst. A24, 321–324 (1968). [CrossRef]
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]
P. Schwander“Efficient interpolation of scattering data to an arbitrary grid,” (in preparation, 2012).
S. Marchesini“Ab initio compressive phase retrieval,” presented at the XXI IUCr Congress, Osaka, Japan, 23–31 Aug. 2008.
P. Bérard, G. Besson, and S. Gallot“Embedding Riemannian manifolds by their heat kernel,” Geom. Funct. Anal.4, 373–398 (1994). [CrossRef]
G. W. Stewart“Error and perturbation bounds for subspaces associated with certain eigenvalue problems,” SIAM Rev.15, 727–764 (1973). [CrossRef]
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].
P. ToppingLecture Notes on Ricci Flow (Cambridge University Press, 2006). [CrossRef]
J. F. M. Svensen“GTM: The generative topographic mapping,” Ph.D. thesis, Aston University (1998).
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]
W. HeisenbergDer Teil und das Ganze (R. Piper & Co.Verlag, 1981).
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]
P. Kostelec and D. Rockmore“FFTs on the rotation group,” Santa Fe Institute working paper #03-11-060 (2003).

Abergel, C.
Adolph, M.
Andersson, I.
Andreasson, J.
Andritschke, R.
Aquila, A.
Arvanitoyeorgos, A.
Bajt, S.
Balasubramanian, M.
Barthelmess, M.
Barty, A.
Belkebir, K.
Belkin, M.
Bérard, P.
Bérard, P. H.
Besson, G.
Biedenharn, L. C.
Bishop, C. M.
Bogan, M. J.
Bostedt, C.
Bott, M.
Boutet, S.
Bozek, J. D.
Bronstein, A. M.
Bronstein, M. M.
Caleman, C.
Cao, H.-D.
Carazo, J.-M.
Casdagli, M.
Chapman, H. N.
Chaumet, P. C.
Chester, D. W.
Chirikjian, G. S.
Claverie, J.
Coifman, R.
Coifman, R. R.
Coppola, N.
Cowley, J. M.
Cromer, D. T.
da Silva, E. A. B.
de Silva, V.
Debenedetti, P. G.
Denker, J. S.
DePonte, D. P.
Doak, R. B.
Donoho, D. L.
Eggermont, P. P. B.
Ekeberg, T.
Elser, V.
Epp, S. W.
Erk, B.
Ferguson, A. L.
Fienup, J. R.
Fischer, N.
Foucar, L.
Frank, J.
Frank, M.
Freiwald, W. A.
Fromme, P.
Fung, R.
Gallot, S.
Gao, H.
Geffrin, J. M.
Gerchberg, R. W.
Giannakis, D.
Giovannini, H.
Girard, J.
Gorke, H.
Gorkhover, T.
Graafsma, H.
Grimes, C.
Gumprecht, L.
Haeberle, O.
Hajdu, J.
Hampton, C. Y.
Hantke, M.
Hartmann, R.
Hau-Riege, S. P.
Hauser, G.
Heisenberg, W.
Herman, G. T.
Herrmann, S.
Hirsemann, H.
Hodgson, K. O.
Holl, P.
Hömke, A.
Howard, R. E.
Hu, B. L.
Hunter, M.
Iwan, B.
Jackel, L. D.
Jönsson, O.
Kevrekidis, I. G.
Khersonskii, V. K.
Kimmel, N.
Kimmel, R.
Kirian, R.
Konevega, A. L.
Kostelec, P.
Krasniqi, F.
Krzywinski, J.
Kühnel, K.
Kuipers, J. B.
Kyatkin, A. B.
Lafon, S.
Lang, S.
Langford, J. C.
LeCun, Y.
Lee, A. B.
Lee, S.
Liang, M.
Lin, T.
Loh, N. T. D.
Lomb, L.
Louck, J. D.
Lovisolo, L.
Maggioni, M.
Maia, F. R. N. C.
Maire, G.
Mann, J. B.
Marchesini, S.
Martin, A.
McCauley, J. L.
Messerschmidt, M.
Miahnahri, A. A.
Michor, P. W.
Misner, C.
Moskalev, A. N.
Moths, B.
Müller, K.-R.
Mumford, D.
Nadler, B.
Natterer, F.
Nilsson, B.
Niyogi, P.
Odic, D.
Oszlányi, F.
Ourmazd, A.
Panagiotopoulos, A. Z.
Phillips, G. N.
Pietschner, D.
Potdevin, G.
Reich, C.
Rocker, A.
Rockmore, D.
Rodnina, M. V.
Rolles, D.
Rosenberg, S.
Ross, W. D.
Roweis, S. T.
Rudek, B.
Rudenko, A.
Rupp, D.
Sabouroux, P.
Saillard, M.
Saldin, D.
Saldin, D. K.
Sauer, T.
Saul, S. K.
Saxton, W. O.
Schaller, G.
Scheres, S. H. W.
Schlichting, I.
Schmidt, C.
Schölkopf, B.
Schopper, F.
Schorb, S.
Schröter, C.
Schulz, J.
Schutz, B. F.
Schwander, P.
Schwartz, E. L.
Seibert, M.
Seltzer, V.
Sentenac, A.
Shah, J.
Shkolnisky, Y.
Shneerson, V.
Shneerson, V. L.
Shoeman, R. L.
Sierra, R. G.
Sigworth, F.
Sigworth, F. J.
Singer, A.
Smola, B.
Solla, S.
Soltau, H.
Spence, J. C. H.
Stark, H.
Starodub, D.
Stern, S.
Stewart, G. W.
Strüder, L.
Süto, A.
Svenda, M.
Svensen, J. F. M.
Svensen, M.
Talneau, A.
Taub, A. H.
Tenenbaum, J. B.
Topping, P.
Tsao, D. Y.
Ullrich, J.
Valle, M.
Varshalovich, D. A.
Vilenkin, N. J.
Wald, R. M.
Warner, F.
Weidenspointner, G.
Weierstall, U.
Westphal, D.
White, T. A.
Wigner, E. P.
Williams, C. K. I.
Williams, G.
Wintermeyer, W.
Yoon, C. H.
Yorke, J. A.
Younes, L.
Zha, H.
Zhu, X.-P.
Zucker, S.

Acta Cryst. A

D. T. Cromer and J. B. Mann“Atomic scattering factors computed from numerical Hartree-Fock wavefunctions,” Acta Cryst. A24, 321–324 (1968). [CrossRef]
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]

Acta Crystallogr.

F. Oszlányi and A. Süto“Ab initio structure solution by charge flipping,” Acta Crystallogr.60, 134–141 (2004). [CrossRef]
B. Moths and A. Ourmazd“Bayesian algorithms for recovering structure from single-particle diffraction snapshots of unknown orientation: a comparison,” Acta Crystallogr.A67 (2011).

Ann. Math.

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

Annu. Rev. Biophys. Biomolec. Struct.

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

Appl. Comput. Harmon. Anal.

R. R. Coifman and S. Lafon“Diffusion maps,” Appl. Comput. Harmon. Anal.21, 5–30 (2006). [CrossRef]
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]

Atti Accad. Naz. Lincei, Cl. Sci. Fis., Mat. Nat., Rend. Lincei, Mat. Appl.

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]

Geom. Funct. Anal.

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

IEE Proc. Vision Image Signal Process.

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]

IEEE Trans. Image Process.

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]

Inverse Probl.

K. Belkebir and M. Saillard“Testing inversion algorithms against experimental data: Inhomogeneous targets,” Inverse Probl.21, S1 (2004). [CrossRef]
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]

J. Mod. Opt.

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

J. Phys.: Condens. Matter

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]

J. Stat. Phys.

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

J. Struct. Biol.

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]

Nat. Methods

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]

Nat. Phys.

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]

Nature

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]
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]

Neural Comput.

M. Belkin and P. Niyogi“Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput.13, 1373–1396 (2003). [CrossRef]
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]
C. M. Bishop, M. Svensen, and C. K. I. Williams“GTM: The generative topographic mapping,” Neural Comput.463, 379–383 (1998).

New J. Phys.

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

Opt. Lett.

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

Optik

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).

Phy. Rev. Lett.

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

Phys. Rev. A

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]

Phys. Rev. D

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

Phys. Rev. E

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

Proc. Natl. Acad. Sci. U.S.A.

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]
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]
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]

Science

W. A. Freiwald and D. Y. Tsao“Functional compartmentalization and viewpoint generalization within the macaque face-processing system,” Science330, 845–851 (2010). [CrossRef] [PubMed]
J. B. Tenenbaum, V. de Silva, and J. C. Langford“A global geometric framework for nonlinear dimensionality reduction,” Science290, 2319–2323 (2000). [CrossRef] [PubMed]
S. T. Roweis and S. K. Saul“Nonlinear dimensionality reduction by locally linear embedding,” Science290, 2323–2326 (2000). [CrossRef] [PubMed]
M. Balasubramanian and E. L. Schwartz“The Isomap algorithm and topological stability,” Science295, 5552 (2002). [CrossRef]

SIAM Rev.

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

Other

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].
P. ToppingLecture Notes on Ricci Flow (Cambridge University Press, 2006). [CrossRef]
J. F. M. Svensen“GTM: The generative topographic mapping,” Ph.D. thesis, Aston University (1998).
P. Kostelec and D. Rockmore“FFTs on the rotation group,” Santa Fe Institute working paper #03-11-060 (2003).
W. HeisenbergDer Teil und das Ganze (R. Piper & Co.Verlag, 1981).
S. Lafon“Diffusion maps and geometric harmonics,” Ph.D. thesis, Yale University (2004).
W. D. RossPlato’s Theory of Ideas (Oxford University Press, 1951). [PubMed]
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.
P. Schwander“Efficient interpolation of scattering data to an arbitrary grid,” (in preparation, 2012).
S. Marchesini“Ab initio compressive phase retrieval,” presented at the XXI IUCr Congress, Osaka, Japan, 23–31 Aug. 2008.
R. M. WaldGeneral Relativity (The University of Chicago Press, 1984).
P. H. BérardSpectral Geometry: Direct and Inverse Problems, (Springer-Verlag, 1989).
S. RosenbergThe Laplacian on a Riemannian Manifold (Cambridge University Press, 1997). [CrossRef]
N. J. VilenkinSpecial Functions and the Theory of Group Representations, (American Mathematical Society, 1968).
D. A. Varshalovich, A. N. Moskalev, and V. K. KhersonskiiQuantum Theory of Angular Momentum (World Scientific, 1988).
J. L. McCauleyClassical Mechanics: Transformations, Flows, Integrable and Chaotic Dynamics (Cambridge University Press, 1997).
J. M. CowleyDiffraction Physics, 3rd ed. (North Holland, 1995).
A. ArvanitoyeorgosAn Introduction to Lie Groups and the Geometry of Homogeneous Spaces (American Mathematical Society, 2003).
J. B. KuipersQuaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality (Princeton University Press, 2002). [PubMed]
S. LangFundamentals of Differential Geometry (Springer-Verlag, 1998).
A. M. Bronstein, M. M. Bronstein, and R. KimmelNumerical Geometry of Non-Rigid Shapes (Springer, 2007).
B. F. SchutzGeometrical Methods of Mathematical Physics (Cambridge University Press, 1980).
S. LangIntroduction to Differentiable Manifolds (Springer-Verlag, 2002).
E. P. WignerGroup Theory and its Application to the Quantum Mechanics of Atomic Spectra (Academic Press, 1959).
L. C. Biedenharn and J. D. LouckAngular Momentum in Quantum Physics (Addison Wesley, 1981).
G. S. Chirikjian and A. B. KyatkinEngineering Applications of Noncummutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups (CRC Press, 2000). [CrossRef] [PubMed]
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.
http://www.youtube.com/watch?v=uat-1voeP3o .
P. Schwander, D. Giannakis, C. H. Yoon, and A. Ourmazd“The symmetries of image formation by scattering. II. Applications,” Opt. Express (2012). (submitted).
F. NattererThe Mathematics of Computerized Tomography (SIAM, 2001). [CrossRef]

2011, Seibert, Nature
2011, Moths, Acta Crystallogr.
2010, Schwander, New J. Phys.
2010, Fischer, Nature
2010, Freiwald, Science
2010, Coifman, Appl. Comput. Harmon. Anal.
2010, Ferguson, Proc. Natl. Acad. Sci. U.S.A.
2010, Singer, J. Struct. Biol.
2010, Girard, Phys. Rev. A
2010, Sentenac, J. Mod. Opt.
2009, Loh, Phys. Rev. E
2009, Geffrin, Inverse Probl.
2009, Saldin, J. Phys.: Condens. Matter
2008, Shneerson, Acta Cryst. A
2008, Coifman, IEEE Trans. Image Process.
2008, Younes, Atti Accad. Naz. Lincei, Cl. Sci. Fis., Mat. Nat., Rend. Lincei, Mat. Appl.
2008, Fung, Nat. Phys.
2007, Scheres, Nat. Methods
2006, Coifman, Appl. Comput. Harmon. Anal.
2005, Coifman, Proc. Natl. Acad. Sci. U.S.A.
2004, Oszlányi, Acta Crystallogr.
2004, Belkebir, Inverse Probl.
2003, Belkin, Neural Comput.
2003, Donoho, Proc. Natl. Acad. Sci. U.S.A.
2002, Frank, Annu. Rev. Biophys. Biomolec. Struct.
2002, Balasubramanian, Science
2001, Lovisolo, IEE Proc. Vision Image Signal Process.
2000, Tenenbaum, Science
2000, Roweis, Science
1998, Schölkopf, Neural Comput.
1998, Bishop, Neural Comput.
1994, Bérard, Geom. Funct. Anal.
1991, Sauer, J. Stat. Phys.
1978, Fienup, Opt. Lett.
1973, Hu, Phys. Rev. D
1973, Stewart, SIAM Rev.
1972, Gerchberg, Optik
1969, Misner, Phy. Rev. Lett.
1968, Cromer, Acta Cryst. A
1951, Taub, Ann. Math.

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.

Click here to see a list of articles that cite this paper

Figures


Fig. 1	Fig. 2	Fig. 3

« Previous Article | Next Article »

OSA is a member of CrossRef.

Select a Conference
Session or Paper #
Year

OpticsInfoBase

Optics Express

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

Article Tools

Article Navigation

Abstract

1. Introduction

2. Conceptual outline

3. Previous work

4. Symmetry-based analysis of scattering data

4.1. Image formation

4.2. Riemannian formulation of image formation

4.3. Symmetries

4.4. Accessing the leading Laplacian eigenfunctions of the homogeneous metric

4.5. Extension to general scattering problems

5. Demonstration of structure recovery in 3D

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

5.2. Robustness against metric inhomogeneity

5.3. Computational cost

6. Conclusions

Appendices

A. The induced metric tensor of scattering data sets

A.1. Derivation

A.2. Decomposition into homogeneous and inhomogeneous parts

A.3. Evaluation of the Lipschitz constant

A.4. The norm of the inhomogeneous term

B. Algorithms

Acknowledgments

References and links

References

Acta Cryst. A

Acta Crystallogr.

Ann. Math.

Annu. Rev. Biophys. Biomolec. Struct.

Appl. Comput. Harmon. Anal.

Atti Accad. Naz. Lincei, Cl. Sci. Fis., Mat. Nat., Rend. Lincei, Mat. Appl.

Geom. Funct. Anal.

IEE Proc. Vision Image Signal Process.

IEEE Trans. Image Process.

Inverse Probl.

J. Mod. Opt.

J. Phys.: Condens. Matter

J. Stat. Phys.

J. Struct. Biol.

Nat. Methods

Nat. Phys.

Nature

Neural Comput.

New J. Phys.

Opt. Lett.

Optik

Phy. Rev. Lett.

Phys. Rev. A

Phys. Rev. D

Phys. Rev. E

Proc. Natl. Acad. Sci. U.S.A.

Science

SIAM Rev.

Other

Cited By

Figures