Abstract We introduce the EMC algorithm for reconstructing a particle's 3D diffraction intensity from very many photon shot-noise limited 2D measurements, when the particle orientation in each measurement is unknown. The algorithm combines a maximization step (M) of the intensity's likelihood function, with expansion (E) and compression (C) steps that map the 3D intensity model to a redundant tomographic representation and back again. After a few iterations of the EMC update rule, the reconstructed intensity is given to the differencemap algorithm for reconstruction of the particle contrast. We demonstrate reconstructions with simulated data and investigate the effects of particle complexity, number of measurements, and the number of photons per measurement. The relatively transparent scaling behavior of our algorithm provides a first estimate of the data processing resources required for future single-particle imaging experiments. I. INTRODUCTION If the goal of single-particle imaging by free electron xray lasers [1] is realized in the next few years, the disciplines of imaging and microscopy will have partly merged with elementary particle physics. Even with the enormous flux of the new light sources, the scattered radiation will be detected as individual photons and hardly resemble diffraction "images" (Figure 1 ). The data in these experiments will instead resemble the particle debris produced in elementary particle collisions. I. INTRODUCTION The particle physics analogy is imperfect, however. Data analysis in elementary particle experiments is complicated more as the result of complex interactions than complexity of the structures -consider the pions produced when a proton is probed with a photon. By contrast, the fundamental interactions between x-ray photons and electrons in a molecule are very simple and the complexity in the analysis of the data is entirely the result of structure. I. INTRODUCTION There are two different data analysis challenges that x-ray laser studies of single-particles will have to face. Consider the two simulated detector outputs shown in Figure 1 . Are the photon counts different because the molecule presented a different orientation to the x-ray beam; is the difference attributable to the statistics of a shot-noise limited signal; or does some combination of the two apply? It is reasonable to conjecture that by collecting sufficiently many data, the orientational and statistical uncertainties can be disentangled to produce molecular reconstructions with acceptable noise and resolution. In this paper we present strong evidence in support of this conjecture by means of an algorithm that succeeds with simulated data. I. INTRODUCTION Due to the length of this paper a survey of its contents may be useful to the reader. Section II explains the theoretical basis of our algorithm whose success is contingent upon an information theoretic noise criterion. Sections III, IV and V respectively describe the test target particles, experimental diffraction conditions and algorithmic parameters used in these single-particle imaging simulations. The limits and encouraging results of these simulations, whose code implementation we elaborate in section VI, are presented in section FIG . 1: (Color online) The same or different? Two simulated measurements (noisy diffraction patterns) in a single particle imaging experiment, where color (white, red, green, blue) represents recorded photon counts (0, 1, 2, 3). Are the differences in the measurements purely statistical, or do they reflect a different view (orientation) of the particle? I. INTRODUCTION VII. Finally, section VIII discusses the scaling of our algorithm's computational requirements with reconstructed resolution. Additional relevant technical details of our paper are recorded in its appendices. II. THEORY The statistical noise and missing orientational information can be addressed by imposing internal consistency of two kinds. First consider the shot noise of the detected signal. Suppose a collection of data sets, such as the pair in Figure 1 , have been identified as candidates for data taken with the molecule in nearly the same orientation. While simply averaging the photon counts yields the continuous signal we are after, we have available the stronger test that the distribution of counts for the measurement ensemble, at each pixel, has the correct Poissonian form. If the test fails, then a different subset of the data must be identified which has this property. Statistical consistency, by itself, is thus a means for classifying like-oriented data sets. II. THEORY The purely statistical analysis makes no reference to the structure implicit in the missing orientational information. This structure begins with the basic fact that the missing information comprises just three continuous variables (e.g. Euler angles), and extends to more detailed constraints, such as the fact that the data samples a signal on a spherical (Ewald) surface in three dimensions and different spherical samples have common values along their intersection, etc. A successful data analysis scheme for the single particle imaging experiments will not just have to signal-average shot noise, but must also reconstruct the missing orientational information by relying on internal consistency associated with the rotation group. The two forms of uncertainty, statistical and orientational, are not independent. In particular, when the statistical noise is large (few detected photons), we expect the reconstruction of the orientational information to be probabilistic in character (i.e. distributions of angles as opposed to definite values). A. Noise criterion A natural question to ask is whether there exists an information theoretic criterion that would apply to any reconstruction algorithm and that can be used to evaluate the feasibility of reconstructions for particular experimental parameters. One of us [2] studied this question for a minimal model with a single rotation angle and obtained an explicit noise criterion formula. Although such a detailed analysis is difficult to extend to the three dimensional geometry of the single-particle imaging experiments, the mathematical statement of the criterion is completely general and, when evaluated numerically by the reconstruction algorithm, serves as a useful diagnostic. We include a brief discussion of the criterion here and refer the reader to the original article for details. A. Noise criterion We recall that the mutual information I(X, Y ) associated with a pair of random variables X and Y is an information theoretic measure of their degree of correlation: I(X, Y ) is the average information in bits that a measurement of X reveals about Y (or conversely). Keeping with the notation of references [2, 3] , we denote the three dimensional intensity distribution by W , the photon counts recorded by the detector on a two dimensional spherical surface by K, and the three unknown parameters that specify the orientation of the surface within the intensity space by Ω. The intensities W have the interpretation of random variables (just as K and Ω), since the particle being reconstructed (and so the associated W ) belongs to a statistical ensemble with known characteristics (size, intrinsic resolution, etc.). A. Noise criterion There are three forms of mutual information that arise in the framework where information about a model W is obtained through measurement of data K that is both statistically uncertain and incomplete (because Ω is not measured). The first is I(K, W ) and measures the information obtained about the model intensities W from a typical unoriented measurement K. A second mutual information is I(K, Ω)| W , the correlation between the measurement K and the orientation Ω conditional on a typical model W . We may also think of I(K, Ω)| W as the entropy of Ω reduced by the finite entropy in its distribution when given typical measurements K and models W . Finally, a simple identity (see appendix A) yields the third form I(K, W )| Ω = I(K, W ) + I(K, Ω)| W (1) as the sum of the other two. The mutual information I(K, W )| Ω is the simplest of the three, as it measures the direct correlation between the continuous signal W and its Poisson samples K because it is conditional on a known orientation Ω. In the limit where the mean photon count per detector pixel is much less than 1, this mutual information is given simply in terms of the total number of photons N detected in an average measurement [2] , A. Noise criterion where γ ≈ 0.577 is Euler's constant. A. Noise criterion In order to sufficiently sample the particle orientations and improve the signal-to-noise, information is accumulated over the course of many measurements. The information delivered in a stream of measurements will initially grow in proportion to the number of measurements, since typically each 2D measurement K samples a different part of the 3D signal W . Two of the mutual information quantities introduced above may therefore be interpreted as information rates: The time unit in these rates is the time for one measurement. The larger of these rates, I(K, W )| Ω , applies to the situation where the noisy data K can simply be signal-averaged to obtain W . From the ratio A. Noise criterion we can assess the reduction in the data rate relative to the signal-averaging scenario. Because this reduction can be severe when shot noise is large, we are primarily interested in the dependence of r on the mean photon number per measurement, N . Not only does an experiment with small r(N ) require a correspondingly larger number of measurements to obtain the same signal-to-noise in the reconstructed particle, our reconstruction algorithm (Section II C) requires many more iterations in this case. Upon using equation (1) , the case r(N ) = 1/2 corresponds to the situation I(K, W ) = I(K, Ω)| W , that is, the information in one unoriented measurement exactly matches the information acquired about its orientation. This interpretation does not imply that reconstruction is impossible for smaller r(N ), since the criterion refers to the properties of a single measurement while the reconstruction algorithm may, in principle, process many measurements in aggregate. Nevertheless, the criterion r(N ) > 1/2 correctly identifies the cross-over region separating easy and hard reconstructions. Using (1) we can rewrite the feasibility criterion in the form A. Noise criterion Our algorithm, based on the expectation maximization principle [4] , evaluates r(N ) with no overhead since the probability distributions in Ω of the measurements K, from which I(K, Ω)| W is derived, are computed in the course of updating the model. When the inequality above is strongly violated we should expect a much lower signal-to-noise in the finished reconstruction than a naive signal-averaging estimate would predict. An important general observation about the noise criterion (4) is that it is remarkably optimistic. As an information measure, I(K, Ω)| W grows only logarithmically with the complexity of the particle. Recall that I(K, Ω)| W is the entropy in Ω of a typical measurement K. Suppose a particle of radius R has its density resolved to contrast elements of size δR. Its rotational structure (in its own space or the Fourier transform space of W ) will then only extend to an angular resolution δR/R. A sampling of the rotation group comprising (R/δR) A. Noise criterion 3 elements thus provides a fair estimate of the entropy and I(K, Ω)| W evaluates to a number of order 3 log (R/δR) [19] . This estimate and equations (2) and (4) imply that values of N of only a few hundred should be sufficient to reconstruct even the most complex particles encountered in biology. B. Classification by cross correlating data The theoretical noise criterion discussed above is beyond the reach of the kind of algorithm that would seem to offer the most direct solution [3] . In this scenario the task is divided into two steps. The first is concerned with classifying the diffraction data into sets that, with some level of confidence, describe the particle in a small range of orientations. After averaging photon counts for the like-sets to improve the signal quality, the diffraction pattern averages would then be assembled into a consistent three dimensional intensity distribution in the second step. B. Classification by cross correlating data The most direct method of assessing the similarity of two diffraction data is to compute the cross correlation. A pair of like-views of the particle would be identified by a large cross correlation. Because this measure also fluctuates as the result of shot noise, its statistical significance must be estimated as well. The result of such an analysis [3] is that the cross correlation based classification can succeed only if the average number of photons per diffraction pattern, N , and the number of detector pixels, M pix , satisfy B. Classification by cross correlating data This criterion imposes a higher threshold on N than the information theoretic criterion (4) because M pix grows algebraically, and not logarithmically, with the complexity of the reconstructed particle. B. Classification by cross correlating data Since the number of measured diffraction patterns will be very large, and the number of pairs to be cross correlated grows as its square, the execution of this approach also seems prohibitive. As Bortel et al. [5] have shown, however, this estimate is overly pessimistic since by selecting suitable representatives of the orientational classes the number of cross correlation computations can be drastically reduced. The expectation maximization (EM) algorithm described below is an alternative classification method where the most time consuming step is again the computation of very many cross correlations. But unlike methods where both vectors of the cross correlation are data and criterion (5) applies, in the EM algorithm only one of the vectors is data while the other is derived from a model. This has the added bonus that the time of the EM calculation is linear, rather than quadratic, in the number of measurements. C. Classification by expectation maximization The algorithm we have developed for the single particle imaging experiments and studied previously in the context of noise limits [2] is based on the idea of expectation maximization (EM) [4] . In general, EM seeks to reconstruct a model from statistical data that is incomplete. The model in the present setting is the intensity signal W , the data are the sets of photon counts K recorded by the detector, and the latter are incomplete because the orientation Ω, of the particle relative to the detector, is not measured. C. Classification by expectation maximization The EM algorithm is an update rule on the model, W → W ′ , based on maximizing a log-likelihood function Q(W ′ ). The algorithm derives its name from the fact that Q(W ′ ) is actually an expectation value of log-likelihood functions, where a probability distribution based on the current model parameters W is applied to the missing data Ω. We will derive Q(W ′ ) for the single particle imaging problem in stages, beginning with the log-likelihood function for the photon counts at a single detector pixel. C. Classification by expectation maximization Let W (q) be the time-integrated scattered intensity at spatial frequency q when the particle is in some reference orientation. The detector pixels, labeled by the index i, approximately measure M pix point samples W (q i ). When multiplied by the pixel area and divided by the photon energy, W (q i ) corresponds to the average photon number recorded at pixel i. Since these normalization factors are constants, we will refer to W interchangeably as "intensity" or "average photon number." If we now give the particle some arbitrary orientation Ω, the average photon number at pixel i is W (R Ω · q i ), where R Ω is the orthogonal matrix corresponding to the rotation between the reference orientation and Ω. Because the implementation of the algorithm approximates the continuous Ω with a discrete sampling of M rot points labeled by the index j, we define W ij = W (R j · q i ) as the average photon number at detector pixel i when the particle has orientation j. C. Classification by expectation maximization The log-likelihood function for the mean photon number W ′ ij , given a photon count K ik at pixel i in measurement k, is the logarithm of the Poisson distribution (apart from an irrel-evant constant): C. Classification by expectation maximization Summing this function over the detector pixels gives the loglikelihood function associated with the joint and independent Poisson distributions on the photons detected in a single measurement (labeled by k): C. Classification by expectation maximization If we knew the orientation j that applied to the counts K ik of measurement k, we would try to maximize the corresponding Q jk with respect to the model values W ′ ij . The EM algorithm deals with the missing information by making an educated estimate of j, for each measurement k, based on the current model values. However, before we enter into these details we should point out that the EM algorithm in our formulation works with many more model parameters than there are in the physical model. That is because W ij and W i ′ j ′ are treated as independent parameters even in the event that the corresponding spatial frequencies R j · q i and R j ′ · q i ′ are nearly the same. This overspecification of parameters will be rectified by the "compression step" described below. C. Classification by expectation maximization The EM algorithm defines the log-likelihood function Q(W ′ ) on the updated model parameters W ′ by assigning a provisional distribution of orientations j to each measurement k based on the current model parameters W . The jdistribution is given as the normalized likelihood function for the measurements K ik conditional on j and the model parameters W . Up to an irrelevant j-independent factor, the conditional probability in question is the product of Poisson probabilities at each detector pixel: C. Classification by expectation maximization The normalized likelihood function allows for an arbitrary prior distribution of the orientations j which we denote by the normalized weights w j : C. Classification by expectation maximization This form is necessary even when the prior distribution on orientations Ω is uniform (the usual assumption for the single particle experiments) because in general the discrete samples j cannot be chosen in such a way that the weights w j are uniform. The EM log-likelihood function may now be written explicitly: C. Classification by expectation maximization Details on the maximization of Q(W ′ ) are given in appendix B; the resulting "maximizing" (M) update rule is simple and intuitive: C. Classification by expectation maximization We see that the data K ik are averaged over all the data sets (k index) with the unknown orientation index j distributed according to probabilities P jk (W ) defined by the current model. It is instructive to check that the update rule applied to an arbitrary rotation of the true signal leaves the signal unchanged (details in appendix B). We now return to the point that the parameters W ij overspecify the true model parameters. For fixed j, the M pix numbers W ij correspond to a tomographic sampling of the 3D space of intensities on a spherical surface with orientation in the 3D space specified by j. To recover a signal in the 3D space we define a "condensation/compression" (C) mapping C. Classification by expectation maximization where p denotes a spatial frequency sampling point in the 3D intensity space. Since the samples p will be arranged on a regular 3D grid, we define interpolation weights f (q) for a general point q in the 3D space which vanish for large |q| and have the property C. Classification by expectation maximization for arbitrary q. Recalling that the value W ij corresponds to the 3D sampling point R j · q i , the signal values after the compression mapping are given by C. Classification by expectation maximization To begin another round of the EM algorithm, after the condensation step, the signal values on the 3D grid have to be "exported/expanded" (E) to the tomographic representation: C. Classification by expectation maximization Using the same interpolation weights and rotation samples j as before, we have C. Classification by expectation maximization The combined mappings E · C : W ij → W ′ ij then have the effect of imposing on the redundant tomographic representation of the signal the property that it is derived from values on a 3D intensity grid. A slightly different way of grouping the three mappings defines one iteration of what we will call the EMC algorithm (Expansion followed by expectation Maximization followed by Compression): C. Classification by expectation maximization The most time consuming step of the EMC algorithm is the computation of the probabilities P jk (W ). Prior to normalization these are the likelihood functions R jk (W ) whose logarithms are given by C. Classification by expectation maximization At the heart of the algorithm we have to compute the cross correlation (sum on i) between the photon counts in each measurement k and the logarithm of the signal at each tomographic sampling (particle orientation) j. Since data are not cross correlated with data, as in some classification methods, the time scaling is linear in the number of measurements. After normalizing to get P jk (W ), the mutual information needed for the noise criterion (4) is obtained without significant additional effort (details in appendix B): C. Classification by expectation maximization (19) The expectation maximization technique described above is very similar to that used by Scheres et al. [6] for cryo-EM reconstructions. Cryo-EM and single-particle x-ray imaging differ in two important physical respects. The first is that the diffraction data in the x-ray experiments has a known origin (zero frequency), thereby reducing the missing information. This is not completely an advantage because the diffraction data, after a successful reconstruction, must undergo an additional stage of phase retrieval before the results can be compared with cryo-EM. The second difference is the noise model that applies to the two techniques. In the absence of background, the shot noise in the x-ray experiments is a fundamental and parameter-free process, whereas the background ice scattering in cryo-EM requires phenomenological models. The expectation maximization algorithm is general enough that these differences do not change the overall structure of the reconstruction process. In fact, the work of Scheres et al. [6] points out that the algorithm is readily adapted to include additional missing data, such as conformational variants of the molecule. C. Classification by expectation maximization Redundant representations of the model parameters, and operations that impose consistency with a physical (3D) model, are also shared features. Scheres et al. [6] obtain the 3D model using ART [7] , a least-squares projection technique. The corresponding operation in our reconstruction algorithm is the linear compression-expansion mapping E · C. The redundancy question did not arise in the same way for the minimal model studied previously [2] , with only a single rotation axis. There the intensity tomographs did not intersect and the speckle structure had to be imposed by an additional support constraint on the Fourier transform of the intensity distribution. C. Classification by expectation maximization Finally, we note that Fung et al. [8] have developed a technique that, like our expectation maximization approach, uses the entire body of data in a single update of the model parameters. III. TEST PARTICLES When simulating the single-particle experiments it is important to distinguish between the resolution limit imposed by the maximum measured scattering angle and the resolution intrinsic to the scattering particle as a result of its dynamics. III. TEST PARTICLES The scattering cross section for a complex molecule is generally significantly smaller, at large momentum transfer, than what is predicted by atomic form factors and a static molecular structure. This phenomenon is well known in crystallography, where the coherent illumination of numerous molecules in various states of perturbation is equivalent -when considering the information recorded in Bragg peaks -to a single molecule with blurred contrast. The same effect, but in the temporal domain, will diminish the scattering at large angles in the single-particle experiments. III. TEST PARTICLES The dynamics of molecules subject to intense x-ray pulses is complicated by the presence of several physical processes [9] . In the case where the degree of ionization of the atoms is relatively low during the passage of the pulse, the x-ray scattering is dominated by the atomic cores and can be analyzed by modeling the atomic motions. Let A k (t) be the amplitude of the incident radiation in a particular momentum mode k. The cross section for scattering a photon into mode k + q with frequency ω contains as a factor the expression III. TEST PARTICLES where f p (q) is the atomic form factor of atom p whose position r p (t) changes with time as a result of large scale ionization, etc. We are interested in modeling the q-dependence of the molecular form factor (20). Without access to detailed simulations of the Coulomb explosion, we have adopted for our data modeling the simple one-parameter form, III. TEST PARTICLES where S(q) is the normalized static (t = 0) structure factor of the molecule. This Gaussian form results if the dynamics of the positions r p (t) can be approximated by independent Gaussian fluctuations over the coherent time scale T of the pulse. The period T , or the time during which the function A k (t)e iωt is approximately constant, is significantly shorter than the pulse duration in a non-seeded free electron laser [10] . III. TEST PARTICLES We expect more detailed dynamical simulations of the scattering cross section to show significant departures from the form above, of a simple Gaussian factor modulating a static structure factor. Rather, the effective structure factor of an exploding molecule should resemble that of an atomistic density that is primarily blurred radially, with contrast at the surface of the molecule experiencing the greatest degradation [9] . Given such complications, our test particle modeling ignores atomicity and treats the particle more simply as a distribution of positive contrast on a specified support with a phenomenologically defined intrinsic resolution given by the form (21). A. Binary contrast particles It is a great convenience, when developing algorithms, to have a simply defined ensemble of problem instances that offers direct control over the key parameters. We have chosen to FIG. 2: Examples of the random binary contrast particles used in our simulations. The contrast is nearly uniform inside a labyrinthine region that fills half the volume of a sphere. Shown are particles of radius R = 4, 8, 12 (left to right), where the dimensionless R is in units of the intrinsic resolution, i.e. the scale of the voxels shown in cross-section for each particle in the lower panel. The particle renderings in this paper, such as those above, show the iso-contrast surface appropriate for the labyrinth walls (half the maximum contrast). A. Binary contrast particles work with an ensemble having a single parameter that controls the complexity of the particle, where our measure of complexity is the dimensionless radius R which specifies the physical particle radius in units of the intrinsic resolution. Our particles have the following properties: A. Binary contrast particles (1) Spherical shape, (2) binary contrast, and (3) Gaussian form factor. A. Binary contrast particles Property (1) is chosen to make the reconstructions as hard as possible, both for the assembly of the 3D intensity and later in the phase retrieval stage (the spherical support offering the fewest constraints [11] ). We chose (2) to mimic a large biomolecule that because of damage can only be resolved into solvent (empty) and non-solvent regions. This property also has the convenience that most of the information about the structure is conveyed by rendering a single 3D contour at an intermediate contrast. Property (3) defines the intrinsic resolution. A. Binary contrast particles The construction of a test particle begins by choosing a value for the dimensionless radius R; the final contrast values will be defined on a cubic grid of size 2R + 1. Our test particle construction algorithm is diagramed in pseudocode (algorithms 1 and 2) . It uses the particle support S (voxels inside the sphere of radius R) and a Gaussian low-pass filter F (q) to impose the form factor (21) on the Fourier transform of the contrast. To keep the dynamic range of the intensity measurements in our simulations constant for different particle sizes R, we parameterize the filter as A. Binary contrast particles where q max = π/R. Since only scattering with |q| < q max is measured, the discarded power is always A. Binary contrast particles In Figure 2 we show examples of binary contrast test particles constructed for three values of the dimensionless radius Output: particle contrast on cubic grid C C ← RandomContrast A. Binary contrast particles Algorithm 2: binary contrast projection R. The largest particles considered in this study had R = 8 because the reconstruction computations grow, in both time and memory, very rapidly with R. In Section 7 we discuss the scaling of the computations with R. B. Degraded resolution biomolecules To put our dimensionless radius R in perspective, the same low-pass filter used for test particles was applied to the roughly 0.8 MDa biomolecule GroEL [12] . After binning the coordinates of the non-hydrogen atoms of the PDB structure on a cubic grid of resolution 2Å, the discrete Fourier transform was computed and truncated at the size 2R + 1. The result was then multiplied by the filter (22) and inverse transformed to give the contrast used in the simulation. Figure 3 shows GroEL processed in this way for three values of R. Handedness in the protein secondary structure begins to appear at about R = 6. These degraded resolution models of GroEL, that mimic the effects of dynamics and a finite duration pulse, are of course completely phenomenological. It may not even be true that the diffraction signal can be modeled by an appropriately blurred contrast function. This will be the case, for example, if the damage dynamics strongly varies with the orientation of the particle. Finally, we cannot ignore the fact that, as a result of thermal motion and solvent, at some level of resolution even the model of a unique (t = 0) diffraction signal breaks down. [12] degraded by the same type of low-pass filter used in the construction of random test particles (Fig. 2) . The axial length of GroEL is approximately 15 nm. At high damage, R = 4 (left), the contrast reveals only the gross particle shape ("cornEL"). Handedness of the protein secondary structure appears at about R = 6 (middle) and is fully evident by R = 8 (right). IV. EXPERIMENTAL PARAMETERS A. Detector parameters The detector geometry, pixel dimensions, and position relative to the scattering particle determine the spatial frequency samples q i of the experimental data. Our simulations use a detector model with three parameters: oversampling factor σ, maximum scattering angle θ, and a dimensionless central data cutoff α. A. Detector parameters The oversampling factor has the most direct interpretation in real space. Oversampling σ corresponds to embedding the particle, with contrast defined on a grid of size 2R + 1, on a grid magnified in size by the factor σ. This also defines the dimensions of the 3D intensity grid, on which most of the computations of the EMC algorithm take place. Since Fourier transforms play no role in these computations there is no incentive to make the dimensions of the intensity grid a product of small primes. It is more natural in the EMC calculations, which have rotational symmetry about zero frequency, to have intensity grids of odd dimension with indices that run between −q max and +q max . Here q max is given by σ R rounded up to the nearest integer. Speckles in the intensity distribution will have a linear size σ in grid units. A. Detector parameters A real detector does not measures point samples with respect to spatial frequency but convolves the true intensity signal with a point spread function defined by the pixel response [13] . To minimize this effect the oversampling in experiments should be kept large. Another reason for keeping σ large is algorithmic: the expansion and compression steps of the EMC algorithm, which interpolate between tomographic and grid samples, introduce errors that are also minimized when the oversampling is large. In this study we used σ = 6. A. Detector parameters The maximum scattering angle is determined by the radius of the detector, L, and the distance D between the particle and the detector, by tan θ = L/D. We define L to be the radius of the largest disk that fits inside the actual detector. This corresponds to discarding data recorded in pixels outside the disk, in the corners of the detector. With this minor truncation of the data, all of it can be embedded in the 3D intensity grid for any particle orientation (relative to the reference orientation). A. Detector parameters The actual choice of spatial frequencies q i used by the EMC algorithm is largely arbitrary, and so we start by considering detector pixels at arbitrary positions [x i , y i ] in the detector plane. Up to a constant factor, the photon momentum detected at pixel i is A. Detector parameters and the corresponding spatial frequency, or momentum transfer from the incident beam, is q i = p i −p 0 , where p 0 is given by (24) with x i = y i = 0. Intensities at these spatial frequencies will be represented as interpolated values with respect to the 3D intensity grid. Since the latter has unit grid spacing, we choose an appropriate rescaling of the q i that is well matched with this. Because most detectors will have pixel positions on a square lattice with some pixel spacing d, our simulations are based on this model. We note, however, that the EMC algorithm operates with general tables of frequencies q i , and whether these are derived from a standard detector or a more complex tiled design is invisible to the workings of the algorithm. For the square-array detector A. Detector parameters where m i and n i are integers, and the rescaled spatial frequencies are given by A. Detector parameters These samples lie on the surface of a sphere that passes through the origin and the scaling is such that samples near the origin match the 3D integer grid: A. Detector parameters The pixels at the edge of the detector have A. Detector parameters and should correspond to frequencies at the highest resolution shell, or |q i | = q max . This condition, evaluated for (25) with D = L cot θ, reduces to A. Detector parameters For a small maximum scattering angle this reduces to the equality between the pixel size of the detector, 2(L/d), and the number of samples in one dimension of the intensity grid, 2q max . The θ-dependence of expression (28) is a result of the spherical shape of the Ewald sphere. The forward scattering by the uniform or uninteresting part of the charge density of a compact particle is so much more intense than the scattering at larger angles from the nonuniform, interesting part, that most detectors need to have the central pixels blocked (beyond what is needed to avoid the incident beam). Figure 4 shows a simulated intensity scan passing through the origin, for one of the test particles described in Section III. The huge central speckle contains essentially only information about the total charge and almost no information about the structure of the particle. A natural size for the detector block is such that scattering at frequencies inside the main speckle is discarded. We obtain the cutoff frequency q min by evaluating the scattering amplitude of a uniform ball having the same radius R as the test particle. The first vanishing of this amplitude determines q min : A. Detector parameters where α ≈ 1.43 is the first non-zero root of πx = tan πx. A. Detector parameters Since q max = σ R, more generally we define A. Detector parameters which shows that the low frequency cutoff is α times the speckle size in grid units (σ). We conclude this section by reviewing the procedure for generating the spatial frequencies q i used by the EMC algorithm. Prior to this a dimensionless test particle radius R has been selected. The half-size of the intensity grid is then given by q max = σ R, and our simulations used σ = 6. Given the maximum scattering angle θ we then determine the detector radius in pixel units, L/d, from (28), as well as the detectorparticle distance D/d using D = L cot θ. All our simulations used θ = 45 A. Detector parameters • . Having determined L/d, we determine (for our choice of square array detector) the indices m i , n i satisfying m A. Detector parameters 2 . These are used in formula (25) to give the table of frequency samples in the reference orientation of the particle. Finally, to model the discarded central data we remove from the table all samples with |q i | < q min , where q min = 1.43σ. B. Diffracted signal strength A key experimental parameter is the flux of photons incident on the particle. For the purpose of simulating the reconstruction process, however, a more convenient form of this parameter is the average number of photons scattered to the detector in one measurement, N . This normalization of the diffraction signal can be carried out once the detector's spatial frequency samples q i are determined. B. Diffracted signal strength In order to generate diffraction data with the property that the mean photon number is N , we first compute the squared magnitude of the Fourier transform of the particle contrast embedded on the intensity grid (having size 2q max ). We interpret the numbers on this grid as the photon flux scattered into the respective spatial frequencies, at this point with arbitrary global normalization. A detector pixel at one such frequency sample will record an integer photon count drawn from the Poisson distribution having the (time and pixel areaintegrated) flux as mean. The quantity we wish to normalize is the net flux at all the detector pixels. When this quantity is N , then the mean photon number per measurement will also be N . B. Diffracted signal strength Because the particle contrast is not spherically symmetric, the net diffracted flux to the detector pixels will fluctuate with the particle orientation. We avoid bias arising from this effect by sampling a few hundred orientations of the particle and applying the associated rotations to the frequency samples in order to estimate the orientation-averaged flux. This number is then used to rescale the flux values on our 3D intensity grid. With this normalization in place, we generate data by repeatedly sampling random orientations, rotating the frequency samples, and then drawing Poisson samples at each of the rotated frequencies for the means given on the normalized intensity grid. Linear interpolation of the grid intensities is used to obtain the diffracted fluxes at the rotated frequencies. V. RECONSTRUCTION PARAMETERS In addition to the diffraction data, prior information about the particle provides additional parameters to the reconstruction algorithm. The only such information we consider in our simulations is the dimensionless particle radius R. This parameter is used in both the intensity reconstruction by the EMC algorithm, as well as the phase retrieval stage that reconstructs the particle contrast from the intensity. A. Rotation group sampling The EMC algorithm orients 2D data tomographs within the 3D intensity distribution using a discrete sampling of the rotation group. An optimal sampling is one where the samples are uniformly distributed and at a sufficient density to resolve the smallest angular features. Because speckles in the intensity distribution have linear dimension σ, features of this size (in voxel units) at the highest resolution shell, q max , determine the angular scale: A. Rotation group sampling The rotation group parameterization that is best suited for generating uniform samplings is based on quaternions [14] . Unit quaternions are points on the unit sphere in four dimensions and encode 2-to-1 the elements of the continuous rotation group in three dimensions. Their key property is the fact FIG. 5: Sampling the 3D rotation group is equivalent to sampling the surface of a sphere in 4D. Shown in the top row is a scheme for sampling the surface of a sphere in one lower dimension based on subdivisions of the 20 faces of the icosahedron. The analogous construction in one higher dimension subdivides the 600 tetrahedral faces of the 600-cell, two examples of which are shown in the bottom row. The resolution of the sampling is specified by the number of subdivisions of each edge; shown are n = 2 (left) and n = 3 (right). A. Rotation group sampling that the distance between quaternions q and q ′ , in the usual sense, is simply related to the angle of the relative rotation between the group elements associated with q and q ′ . For small relative rotations δθ this relationship is: A. Rotation group sampling Given a δθ, the problem of selecting rotation group samples, such that any rotation is within a relative rotation δθ of some sample, is thus equivalent to the standard problem of constructing efficient coverings [15] of the 3-sphere. We solve this covering problem by using a design based on a highly symmetric polytope, the 600-cell [16] . This polytope is the four dimensional analog of the icosahedron in that it approximates the curved surface of the sphere by a union of regular simplices -3D tetrahedra rather than triangles in four dimensions. The regular tetrahedron is efficiently covered by points in the fcc arrangement; coverings with increasing resolution are shown in Fig. 5 . The resolution of the covering is parametrized by an integer n that gives the number of subdivisions of each edge of the tetrahedron. Our 3-sphere coverings are obtained by rescaling the points that cover the tetrahedral faces of the 600-cell to unit length. Details of the construction, including the computation of the sample weights, are given in appendix C. There are only two properties of the rotation group sampling that have direct relevance to the EMC algorithm for intensity reconstruction: the angular resolution δθ and the number of rotation samples, M rot . Defining δθ as the covering radius of the sampling, the n-dependence is given by (see appendix C): A. Rotation group sampling When combined with the estimate (31), this implies that n should roughly coincide with the dimensionless particle radius R. Moreover, since n ≈ R, the number of samples (see appendix C), A. Rotation group sampling grows in proportion with the volume of the particle. B. Particle support Our phase reconstruction of the complex diffraction amplitude is carried out with the diffraction magnitude on the same grid as used by the EMC algorithm for the intensity reconstruction. The support constraint is therefore that the particle contrast can be non-zero only within a sphere of radius R grid units. In our simulations, which were limited to R ≤ 8, we increased the support radius by one or two units because precise knowledge of the support is usually not available in real experiments. VI. RECONSTRUCTION ALGORITHM Our algorithm for reconstructing the scattering contrast of a particle begins by reconstructing the 3D intensity with the EMC algorithm for classifying diffraction data. This section describes in concise algorithmic language the EMC process already sketched in Section II C. For the relatively much easier final step, of reconstructing the particle contrast from the intensity, we use the difference-map (DM) phase reconstruction algorithm. A short description of the DM algorithm, described in greater detail elsewhere [17] , is included for completeness. A. EMC intensity reconstruction The EMC algorithm builds a model of the 3D intensity from a large collection of non-oriented, shot-noise limited diffraction data. The orientational classification of the data is probabilistic, where the data are assigned probability distributions in the rotation group and these are systematically refined so as to maximize the likelihood of the intensity model. The EMC algorithm comprises three steps: E-step: Expand the grid intensities into the tomographic representation: We use pseudocode to describe these steps in the next sections. The notation matches the theoretical discussion in Section II C. Spatial frequencies are denoted by q and p, detector pixel indices by i, rotation group samples by j, and k is always a data index. Algorithm 3: E-step: model expansion E-step: model expansion In the E-step the grid model of the intensities is expanded into a redundant tomographic representation (model) to make the expectation maximization step (M) easier. Intensities W ij in the tomographic model are treated as independent variables by the M-step. E-step: model expansion Each element of the tomographic model is associated with a particular detector spatial frequency q i and rotation matrix R j . The M pix frequencies q i refer to the detector (or particle) in an arbitrary reference orientation; the M rot matrices R j are rotations relative to the reference orientation. The construction of the q i for a simple square array detector is given in Section IV. Our rotation matrices are generated from precomputed lists of quaternions that sample the rotation group at the desired resolution (see appendix C). We use linear interpolation to extract intensity values at the rotated spatial frequencies q ′ = R j · q i . M-step: expectation maximization The probabilistic classification of the data, and then their aggregation into an improved tomographic model, is performed in the M-step. Central in this process is the computation of the conditional probabilities P jk . These are based on the current intensity model, W ij . When the diffraction data (photon counts) K ik are averaged with respect to these probabilities (equation (11)), the result is a tomographic model W ′ ij with increased likelihood. M-step: expectation maximization The most time-intensive parts of the computation, and indeed of the whole reconstruction algorithm, are the nested loops over k, j, and i that would imply an operation count that scales as M data × M rot × M pix . However, the innermost loop, on the pixel index i, can be greatly streamlined in both places where it occurs by skipping all the pixels that have zero photons. We use a sparse representation of the photon counts that reduces the time scaling to M data × M rot × N , since most non-zero counts will be a single photon and the average total photon number is N . M-step: expectation maximization Two copies of the intensity model are held in memory at any time: the current model for conditional probabilities, and the updated model obtained by photon averaging. In the innerInput: tomographic model Wij, data K ik , rotation group weights wj Output: updated model W ′ ij , mutual information I I ← 0 for j ← 1 to Mrot do Sj ← 0 M-step: expectation maximization Algorithm 4: M-step: expectation maximization most loop computations of the conditional probabilities only the logarithm of the current model is used. The actual computation in this most time-intensive step involves incrementing the conditional probabilities P jk by log W ij for the pixels i that recorded photons in diffraction pattern k (or a multiple of this if multiple photons were recorded). After the conditional probability for a particular k is computed, the second timeintensive step is executed. In this the updated model W ′ ij is incremented by P jk , again, for only the pixels i where photons were recorded (or a multiple of this). M-step: expectation maximization The pseudocode shows how directly the mutual information I(K, Ω)| W is computed from the conditional probabilities P jk . In Section VII B we show how this quantity provides a useful diagnostic for reconstructions in addition to having intrinsic value as a measure of information. There are a few places not shown in the pseudocode that require special attention in the implementation. As an example, it is important to check for over/underflow in the computation of the conditional probabilities when the logarithms of the not yet normalized probabilities are exponentiated. M-step: expectation maximization Input: data index k, tomographic model Wij, data K ik , rotation group weights wj Output: M-step: expectation maximization Algorithm 5: conditional probability C-step: model compression The C-step (14) is the reverse of the model expansion, or Estep, and both of these operations use far less time than the Mstep that comes in between. Over the course of multiple EMC iterations, the combination of C-step followed by E-step has the effect of making the tomographic model of the intensity, W B. Phase retrieval We use the difference-map algorithm [17] to reconstruct the phases associated with the Fourier magnitudes obtained by the EMC algorithm, as well as the Fourier magnitudes in the central missing data region (q < q min ). B. Phase retrieval Our pseudocode for the difference-map emphasizes its generic character as a method for reconstructing models subject to two constraints. One constraint, provided by the EMC intensities, is the Fourier magnitude constraint. The difference map implements this constraint by the operation FourierProj.
{'paper_id': '119204426', 'title': 'A reconstruction algorithm for single-particle diffraction imaging experiments', 's2_url': 'https://api.semanticscholar.org/CorpusID:119204426', 'source': 'S2ORC'}