## Improved success rate and stability for phase retrieval by including randomized overrelaxation in the hybrid input output algorithm |

Optics Express, Vol. 20, Issue 15, pp. 17093-17106 (2012)

http://dx.doi.org/10.1364/OE.20.017093

Acrobat PDF (919 KB)

### Abstract

In this paper, we study the success rate of the reconstruction of objects of finite extent given the magnitude of its Fourier transform and its geometrical shape. We demonstrate that the commonly used combination of the hybrid input output and error reduction algorithm is significantly outperformed by an extension of this algorithm based on randomized overrelaxation. In most cases, this extension tremendously enhances the success rate of reconstructions for a fixed number of iterations as compared to reconstructions solely based on the traditional algorithm. The good scaling properties in terms of computational time and memory requirements of the original algorithm are not influenced by this extension.

© 2012 OSA

*non-destructive*tool for the investigation of structural properties of matter because they exhibit high penetration depth and high spatial resolution [1

1. F. v. d. Veen and F. Pfeiffer, “Coherent x-ray scattering,” Phys J..: Condens. Matter **16**, 5003–5030 (2004). [CrossRef]

^{rd}generation synchrotrons [4] provide brilliant x-ray beams with a very high degree of coherence and with very high flux, so that even dot- and wire-like nanostructures can be investigated [2

2. R. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A **7**, 394–411 (1990). [CrossRef]

5. I. Robinson and R. Harder, “Coherent x-ray diffraction imaging of strain at the nanoscale,” Nat Mater **8**, 291–298 (2009). [CrossRef] [PubMed]

11. A. A. Minkevich, E. Fohtung, T. Slobodskyy, M. Riotte, D. Grigoriev, M. Schmidbauer, A. C. Irvine, V. Novák, V. Holý, and T. Baumbach, “Selective coherent x-ray diffractive imaging of displacement fields in (Ga,Mn)As/GaAs periodic wires,” Phys. Rev. B **84**, 054113 (2011). [CrossRef]

## 1. The phase retrieval problem

*f*

_{in}(

*x⃗*) in

*d*-dimensional direct space (“position space”). We assume that (i) the shape 𝕊 of

*f*

_{in}(

*x⃗*) (i.e., the smallest domain in direct space for which

*f*

_{in}(

*x⃗*) ≠ 0) and (ii) the quantity

*A*≡ |

_{k⃗}**FT**{

*f*

_{in}(

*x⃗*)}| (i.e., the amplitudes of its Fourier transform) are known. It has been proven that this information is sufficient to reconstruct the object

*f*

_{in}(

*x⃗*)

*if*the shape 𝕊 is

*finite*and the dimension

*d*of direct space is at least two [2

2. R. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A **7**, 394–411 (1990). [CrossRef]

17. R. P. Millane, “Multidimensional phase problems,” J. Opt. Soc. Am. A **13**, 725–734 (1996). [CrossRef]

*x⃗*inside the object domain 𝕊 corresponds to (up to) two real unknowns (magnitude and phase). However, outside the domain 𝕊,

*f*

_{in}(

*x⃗*) is precisely zero for all positions

*x⃗*. Hence, each point outside 𝕊 defines two real equations for the determination of the

*N*real phases Φ

*, if we require*

_{k⃗}*f*

_{in}(

*x⃗*) = 0 ∀

*x⃗*∉ 𝕊. Therefore, we can hope to reconstruct the missing phases Φ

*on the sampled grid 𝕄 once where*

_{k⃗}*N*

_{𝕊}is the number of points inside the region 𝕊. The fraction

*σ*=

*N/N*

_{𝕊}is called oversampling ratio. From our elementary discussion, we can conclude that

*σ*= 2 is a lower bound for a successful reconstruction, if no additional a priori knowledge is available. For more details on oversampling, we refer the reader to the investigations of Elser et Milliane [21

21. V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr., Sect. A: Found. Crystallogr. **64**, 273–279 (2008). [CrossRef]

22. J. Miao, D. Sayre, and H. N. Chapman, “Phase retrieval from the magnitude of the Fourier transforms of nonperiodic objects,” J. Opt. Soc. Am. A **15**, 1662–1669 (1998). [CrossRef]

*f*

_{in}(

*x⃗*) and the modulus

*A*of the Fourier transform of

_{k⃗}*f*

_{in}(

*x⃗*) on a mesh 𝕄 that satisfies Eq. (2), we try to reconstruct the phases Φ

*and, thus, the object*

_{k⃗}*f*

_{in}(

*x⃗*).

## 2. Reconstruction algorithms

12. J. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. **21**, 2758–2769 (1982). [CrossRef] [PubMed]

13. J. Fienup, “Reconstruction of a complex-valued object from the modulus of its Fourier transform using a support constraint,” J. Opt. Soc. Am. A **4**, 118–123 (1986). [CrossRef]

### 2.1. Hybrid input output and error reduction

*i*) of this algorithm, which is called error reduction (ER) algorithm [12

12. J. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. **21**, 2758–2769 (1982). [CrossRef] [PubMed]

**P**

_{𝕊}and

**P**

*are projection operators in direct space and reciprocal space respectively, i.e., and For notational simplicity, we assume that any operand of*

_{A}**P**

*or*

_{A}**P**

_{𝕊}is transformed to the proper space (i.e., Fourier transform to reciprocal or direct space respectively) before the operator

**P**

*or*

_{A}**P**

_{𝕊}is applied (e.g.,

**P**

*is*

_{A}*non-linear*,

*non-convex*and

*non-unique*[24

24. H. H. Bauschke, P. L. Combettes, and D. R. Luke, “Phase retrieval, error reduction algorithm, and fienup variants: a view from convex optimization,” J. Opt. Soc. Am. A **19**, 1334–1345 (2002). [CrossRef]

*A*(see Eq. (18)). The ER-algorithm is a local minimizer of a suitable chosen error metrics [12

_{k⃗}12. J. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. **21**, 2758–2769 (1982). [CrossRef] [PubMed]

13. J. Fienup, “Reconstruction of a complex-valued object from the modulus of its Fourier transform using a support constraint,” J. Opt. Soc. Am. A **4**, 118–123 (1986). [CrossRef]

*f*

_{in}(

*x⃗*), but to some local minimum. In addition, the error metric may stagnate for many iterations before decreasing further. More information on stagnation problems and the ER-algorithm can be found in [12

**21**, 2758–2769 (1982). [CrossRef] [PubMed]

13. J. Fienup, “Reconstruction of a complex-valued object from the modulus of its Fourier transform using a support constraint,” J. Opt. Soc. Am. A **4**, 118–123 (1986). [CrossRef]

23. J. Fienup and C. Wackermann, “Phase-retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A **3** (1986). [CrossRef]

**21**, 2758–2769 (1982). [CrossRef] [PubMed]

**4**, 118–123 (1986). [CrossRef]

23. J. Fienup and C. Wackermann, “Phase-retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A **3** (1986). [CrossRef]

*β*is a real parameter typically chosen in the range [0.5; 1.0] [23

23. J. Fienup and C. Wackermann, “Phase-retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A **3** (1986). [CrossRef]

22. J. Miao, D. Sayre, and H. N. Chapman, “Phase retrieval from the magnitude of the Fourier transforms of nonperiodic objects,” J. Opt. Soc. Am. A **15**, 1662–1669 (1998). [CrossRef]

25. H. Takajo, T. Takahashi, R. Ueda, and M. Taninaka, “Study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A **15**, 2849–2861 (1998). [CrossRef]

26. H. Takajo, T. Takahashi, and T. Shizuma, “Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A **16**, 2163–2168 (1999). [CrossRef]

*N*

_{HIO}iterations of the HIO-algorithm followed by

*N*

_{ER}iterations of the ER-algorithm. This combination is more successful than both algorithms on their own as it was observed in practice [13

**4**, 118–123 (1986). [CrossRef]

**3** (1986). [CrossRef]

### 2.2. Hybrid input output with randomized overrelaxation ((HIO+O_{R})+ER)

14. A. Levi and H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A **1**, 932–943 (1984). [CrossRef]

15. D. C. Youla and H. Webb, “Image restoration by the method of convex projections: part 1 – theory,” IEEE Trans. Med. Imaging **1**, 81 –94 (1982). [CrossRef] [PubMed]

27. V. Elser, “Phase retrieval by iterated projections,” J. Opt. Soc. Am. A **20**, 40–55 (2003). [CrossRef]

**P**

*by where*

_{μ}*λ*is a real constant called

_{μ}*relaxation parameter*[14

14. A. Levi and H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A **1**, 932–943 (1984). [CrossRef]

**Q**

*→*

_{μ;λμ}**P**

*is obtained for*

_{μ}*λ*→ 1.

_{μ}15. D. C. Youla and H. Webb, “Image restoration by the method of convex projections: part 1 – theory,” IEEE Trans. Med. Imaging **1**, 81 –94 (1982). [CrossRef] [PubMed]

14. A. Levi and H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A **1**, 932–943 (1984). [CrossRef]

27. V. Elser, “Phase retrieval by iterated projections,” J. Opt. Soc. Am. A **20**, 40–55 (2003). [CrossRef]

28. S. Marchesini, “Invited article: A unified evaluation of iterative projection algorithms for phase retrieval,” Rev. Sci. Instrum. **78**, 011301 (2007). [CrossRef] [PubMed]

*λ*=

_{A}*λ*

_{𝕊}=

*β*

^{−1}[27

27. V. Elser, “Phase retrieval by iterated projections,” J. Opt. Soc. Am. A **20**, 40–55 (2003). [CrossRef]

28. S. Marchesini, “Invited article: A unified evaluation of iterative projection algorithms for phase retrieval,” Rev. Sci. Instrum. **78**, 011301 (2007). [CrossRef] [PubMed]

29. S. Marchesini, “Phase retrieval and saddle-point optimization,” J. Opt. Soc. Am. A **24**, 3289–3296 (2007). [CrossRef]

**P**

*in reciprocal space in the HIO-algorithm itself by its relaxed expression The direct space assembly in Eq. (5) of the HIO-algorithm remains unchanged. This corresponds to changing Eq. (6) to If we rewrite this expression in the projectors*

_{A}**P**

_{𝕊}and

**P**

*, we get*

_{A}*β*(

*λ*− 1) from the identity operator in the first term can neither be represented by the traditional HIO-algorithm for any value of

_{A}*β*(see Eq. (6)) nor by the difference map algorithm for any (

*β*,

*λ*,

_{A}*λ*

_{𝕊}) (see Eq. (8)). In both cases, the previous iterative result

**P**

_{𝕊}) or reciprocal space (

**P**

*) before being included in the calculation for*

_{A}*λ*in Eq. (9). If we restrict to a fixed set of values

_{A}*λ*for all iterations, we risk simply exchanging one trap by another or one local minimum by another. Trying to overcome local minima and stagnation, we propose a new approach: For each iteration, we

_{A}*randomly*select the parameter

*λ*. More precisely, for the remainder of this paper, we investigate a uniform random distribution in the range [1 −

_{A}*ν*, 1 +

*ν*],

*ν*≥ 0, for

*λ*which is reassigned each iteration. Unless stated otherwise, we choose

_{A}*ν*= 0.5. Note, that a fixed value

*λ*≡ 1 for all iterations corresponds to the usual HIO-algorithm. In order to distinguish our new extension from the traditional HIO-algorithm, we call our extension HIO+O

_{A}_{R}-algorithm. The power of this extension is strongly supported by the fact, that the HIO+O

_{R}-algorithm is capable of reconstructing objects without including the ER-algorithm with significant success rates. If the HIO+O

_{R}-algorithm is combined with ER, we call the algorithm (HIO+O

_{R})+ER-algorithm (see Fig. 1).

*Ĥ*

_{HIO+OR}(

*β*,

*λ*) to the other algorithms which have been proposed [28

_{A}28. S. Marchesini, “Invited article: A unified evaluation of iterative projection algorithms for phase retrieval,” Rev. Sci. Instrum. **78**, 011301 (2007). [CrossRef] [PubMed]

**1**, 932–943 (1984). [CrossRef]

*λ*and, therefore, should change from iteration to iteration as a consequence of randomization. Thus, stagnation in a specific trap or tunnel is strongly reduced, as most traps and tunnels are no longer persistent throughout the iterative reconstruction process. However, the true solution

_{A}*f*

_{in}(

*x⃗*) is a fixed point of the iterative procedure defined in Eq. (11) for

*all*values of

*λ*.

_{A}### 2.3. Projection polynomials

_{R})+ER-algorithm is based on two ingredients: overrelaxation and randomization. In order to gain a deeper understanding of the (HIO+O

_{R})+ER-algorithm, it is useful to investigate both ingredients separately. Studying the HIO-algorithm extended by overrelaxation of

**P**

*, but without randomization is straight forward: we simply keep a fixed, predefined overrelaxation parameter*

_{A}*λ*throughout the entire iterative reconstruction process. In this section, we present a framework for randomization of iterative projection algorithms performed in a way which is not based on overrelaxation of

_{A}**P**

*. Although this framework can be applied for studying randomization of any iterative projection algorithm, we limit our numerical simulations (in section 4) to parameter values whose deterministic contribution coincides the traditional HIO-algorithm.*

_{A}*p*is the maximum number of successive projection operators which should be included in

*Ĥ*

_{Proj}.

*any*combination of projection operators

*ξ*∈ {𝕊,

_{j}*A*},

*j*∈ {1,...,

*m*}, reduces to one of the four building blocks

**P**

_{𝕊}(

**P**

_{A}**P**

_{𝕊})

*,*

^{n}**P**

*(*

_{A}**P**

_{𝕊}

**P**

*)*

_{A}*, (*

^{n}**P**

_{𝕊}

**P**

*)*

_{A}*and (*

^{n}**P**

_{A}**P**

_{𝕊})

*for some integer*

^{n}*n*≥ 0. This is a consequence of the defining property

**P**

*and*

_{A}**P**

_{𝕊}) is no longer idempotent. The special case of the identity operator 1 and a single projection operator is included for the case

*n*= 0 in those building blocks. However, the identity operator is included twice, namely for

*n*= 0 for (

**P**

_{𝕊}

**P**

*)*

_{A}*and (*

^{n}**P**

_{A}**P**

_{𝕊})

*. Therefore, one spurious coefficient in the projection polynomial is introduced if both building blocks are included for*

^{n}*n*= 0. This is avoided by restricting those two building blocks to

*n*≥ 1 and including the identity operator separately. Therefore, Eq. (12a) represents the most general polynomial expression which contains a maximum of

*q*successive projections of two different kinds, if we incorporate the idempotence of projection operators.

*f*

_{in}(

*x⃗*) is a fixed point of

*Ĥ*

_{Proj}for any choice of its parameters (

*b*,

*c⃗*

_{𝕊},

*c⃗*), it is necessary to enforce one constraint on the coefficients: If the input for the projection operators

_{A}**P**

_{𝕊}and

**P**

*coincides with the true solution*

_{A}*f*

_{in}(

*x⃗*), the projection operators

**P**

_{𝕊}and

**P**

*reduce to the identity operator 1. Therefore, given the true solution*

_{A}*f*

_{in}(

*x⃗*) as input, the operator

*Ĥ*

_{Proj}simplifies to the identity operator 1 for any choice of its parameters (

*b*,

*c⃗*

_{𝕊},

*c⃗*)

_{A}*if and only if*the additional constraint is fulfilled. Consequently, for a maximum of

*p*successive projections in the projection polynomial

*Ĥ*

_{Proj}, only 2

*p*free parameters appear in

*Ĥ*

_{Proj}by incorporating the idempotence of projection operators.

## 3. Monitoring convergence of the reconstruction

*f*

^{(i)}from iteration (

*i*− 1) to iteration (

*i*). Second, we measure the mathematical distance to the (sampled) true solution

*f*

_{in}(

*x⃗*). And last, but not least, we measure the deviation in reciprocal space between the a priori given reciprocal input data

*A*and the magnitude of the Fourier transform of the reconstructed object. All three parameters yield different information:

_{k⃗}*f*

^{(i)}after iteration (

*i*) to the true direct space object

*f*

_{in}is, of course, the best measure for the quality of the reconstructed image. We define this mathematical distance by an angle The absolute value in the nominator of the argument of the arccos eliminates the influence of the undetermined global phase in

*f*

^{(i)}. Moreover,

*φ*

^{(i)}is identical in direct and reciprocal space (invariance of scalar product upon unitary basis transformations like the Fourier transform).

*ε*

^{(i)}which depends only on the a priori known (measured) amplitudes

*A*and not on the true direct space solution

_{k⃗}*f*

_{in}(

*x⃗*) is where ||·||

*is the*

_{p}*p*-norm. Since the construction of the absolute value is a non-linear, non-invertible map, the result can in general be quite different from the angle defined above. In fact, two quite different direct space objects

*f*

_{in}(hence quite different complex Fourier transforms) may posses an extremely similar distribution of the magnitude

*A*in reciprocal space [16

16. A. A. Minkevich, T. Baumbach, M. Gailhanou, and O. Thomas, “Applicability of an iterative inversion algorithm to the diffraction patterns from inhomogeneously strained crystals,” Phys. Rev. B **78**, 174110 (2008). [CrossRef]

18. J. H. Seldin and J. R. Fienup, “Numerical investigation of the uniqueness of phase retrieval,” J. Opt. Soc. Am. A **7**, 412–427 (1990). [CrossRef]

*f*

^{(i)}from iteration to iteration is very important, too. This must not be confused with the change of the non-invertible map

*ε*

^{(i)}from iteration to iteration: Moving along a connected line of constant error metric does not change the error metric itself, but the reconstructed object

*f*

^{(i)}may change arbitrarily. Nevertheless, the algorithm may converge (i.e. no change from iteration to iteration), but not to the true solution

*f*

_{in}of the problem [14

**1**, 932–943 (1984). [CrossRef]

16. A. A. Minkevich, T. Baumbach, M. Gailhanou, and O. Thomas, “Applicability of an iterative inversion algorithm to the diffraction patterns from inhomogeneously strained crystals,” Phys. Rev. B **78**, 174110 (2008). [CrossRef]

*f*

_{in}by Eq. (17). A suitable choice for observing the change from iteration to iteration is given by the angle In contrast, the

*p*-norm

*i*− 1) to iteration (

*i*).

## 4. Numerical examples

*ξ*(

*x⃗*) is a

*real*function and Ω

_{𝕊}(

*x⃗*) is the shape function The reconstruction of the first phase object (see Fig. 2(a)) is plagued by (at least) one strong local minimum far away from the true solution

*f*

_{in}which results in severe problems for the traditional HIO+ER-algorithm. The reconstruction of the second phase object (see Fig. 2(b)) is plagued by many local minima near the perfect solution

*f*

_{in}, in particular, by stripes [23

**3** (1986). [CrossRef]

*π*extend over several sampling points. As a third test object, we investigate a purely real object

*f*

_{in}(

*x⃗*) with strong variation of its magnitude over very short length scales and a different shape (see Fig. 3(a)). In fact, the success rate of the traditional HIO-algorithm without randomized overrelaxation was lowest for this third example (see Fig. 3(b) and Fig. 4). From the numerical results, we conclude that randomized overrelaxation is a powerful extension for a wide class of objects and not only for objects possessing some particular features.

*ξ*

_{1}is defined according to Eq. (20) and the parameters were chosen as

*b*

_{1}= 1.5515 and

*c*

_{1}= −1.835. The shape 𝕊 has been restricted to the triangular region defined by (0, 0), (0,

*a*) and (

*a*, 0) with

*a*= 0.97. The object has been sampled on an equidistant grid with

*N*

_{1}×

*N*

_{2}= 256 × 256 data points in the interval (

*x*,

*y*) = (−1, −1) to (

*x*,

*y*) = (1, 1). The resulting object is depicted in Fig. 2(a).

*b*

_{2}= −0.3515 and

*c*

_{2}= 0.535. The phase field in this case is depicted in Fig. 2(b).

*φ*

^{(i)}to the input object (see Eq. (17)) falls below some given limit

*φ*

_{Converged}(=0.05° unless stated otherwise). We repeat the reconstruction process for

*N*

_{Real}initial trials (random phases at each

*k⃗*-point, amplitudes

*A*). Finally, we calculate the success rate which tells us the percentage of reconstruction processes that have been successful up to iteration (

_{k⃗}*i*). A good reconstruction algorithm

- should reach a success rate of almost 100%,
- should not depend on the starting point (as long as no good starting point is available),
- should perform the reconstructions with little computational effort and
- should possess these properties for a wide range of its internal parameters (i.e.,
*β*,*ν*,*N*_{HIO}and*N*_{ER}in case of the (HIO+O_{R})+ER-algorithm).

_{R})+ER-extension can be implemented very efficiently exploiting the good scaling properties of the FFT-algorithm. Therefore, as long as the number of iterations is not too high, the third requirement is clearly met by both, the HIO+ER and (HIO+O

_{R})+ER-algorithm.

_{R})+ER-algorithm for different internal parameters in Fig. 4. We normalized the computational effort, i.e., one iteration of the (HIO+O

_{R})+ER-algorithm with

*N*

_{HIO}= 130 and

*N*

_{ER}= 10 corresponds to two successive iterations with

*N*

_{HIO}= 50 and

*N*

_{ER}= 20. This prefactor of 2 can be found in the legend of the graph in front of the square brackets for each calculation.

*N*

_{HIO}and

*N*

_{ER}: in contrast to the HIO based calculations, it quickly converged to 100%. In fact, overrelaxation is so powerful that stagnation in the HIO-algorithm is eliminated entirely and intermediate ER-iterations are no longer necessary (see black dash-dotted curve in Fig. 4). The success rate of the traditional HIO+ER-algorithm stagnates on some level far below 100%. This stagnation is significant in the long term behavior, as we illustrate in Fig. 5 by plotting the success rate of the traditional HIO+ER-algorithm for 50 times as many iterations as in Fig. 4(a). Note, that all trials that did not converge after 2500 iterative steps using the traditional HIO+ER-algorithm with

*N*

_{HIO}= 130 and

*N*

_{ER}= 10 in Fig. 5 are separated from the true solution by an angle greater than

*φ*= 55°.

*N*

_{HIO}= 130 and

*N*

_{ER}= 10, the success rate of the traditional HIO+ER-algorithm is even slightly superior to the (HIO+O

_{R})+ER-extension, but for this specific set of parameters, the success rate converges to 100% very quickly for both algorithms. However, for the set of parameters (

*N*

_{HIO}= 50,

*N*

_{ER}= 20) and (

*N*

_{HIO}= 40,

*N*

_{ER}= 30), the success rate quickly converges to 100% only for the (HIO+O

_{R})+ER-algorithm, but not for the HIO+ER-algorithm. Hence, the (HIO+O

_{R})+ER-algorithm is much more stable with respect to the particular choice of the internal parameters

*N*

_{HIO}and

*N*

_{ER}including, in particular, the case

*N*

_{ER}= 0.

*φ*

_{Converged}≤ 0.05° to determine successful reconstructions. The (HIO+O

_{R})+ER-algorithm is much more successful and reaches success rates of 100% with few iterations (see Fig. 3(b)). Furthermore, reaching the success rate of 100% does not sensitively depend on the internal parameters

*N*

_{HIO}and

*N*

_{ER}. Again, keeping

*N*

_{ER}small compared to

*N*

_{HIO}or eliminating ER-iterations completely yields the best results. Keep in mind, that neither the reality constraint nor the positivity constraint of the object have been exploited during reconstruction.

*f*

_{in}basically evolved towards the correct direction. However, at some point, stagnation in form of stripes close to the true solution

*f*

_{in}appeared. These stripes are very persistent and prevent the usual HIO+ER-algorithm from further convergence to the true solution

*f*

_{in}. Typically, the mathematical distance

*φ*of the objects containing stripes to the true solution

*f*

_{in}is in the order of 0.05 to 5.0 degrees. In case of the purely real test object, after 150 iterations all reconstructed objects reached a distance

*φ*≤ 0.5° (= 10 ·

*φ*

_{Converged}) for HIO

_{130}− ER

_{10}and 31% for HIO

_{50}− ER

_{20}. The remaining 71% of the objects for HIO

_{50}− ER

_{20}reached a distance

*φ*≤ 5° (= 100 ·

*φ*

_{Converged}) using traditional HIO+ER-algorithm and 150 iterations. Note, that the change

*χ*

^{(}

^{i}^{)}(see Eq. (19)) from iteration to iteration does not vanish, i.e. numerically, the algorithm did not converge within the given number of iterations.

_{R})+ER-algorithm for different values of the parameter

*ν*. In addition, Fig. 6(b) depicts the success rate for different values of the parameter

*β*. Within the range

*β*∈ [0.5, 1.0], which is typically used in the traditional HIO+ER-algorithm, the (HIO+O

_{R})+ER-extension does not sensitively depend on the particular choice of

*β*. Therefore, the (HIO+O

_{R})+ER-algorithm does not depend sensitively on any of its internal parameters

*N*

_{HIO},

*N*

_{ER},

*β*and

*ν*. Hence, it fulfills all four requirements on a good reconstruction algorithm which we stated above.

*λ*. We see extremely sensitive behavior of the success rate on the precise value of

_{A}*λ*if it is kept fixed. Whereas increasing

_{A}*λ*up to 1.02 improved the success rate for the first object, it completely vanished for

_{A}*λ*= 1.01 for the second phase object. For a deviation from 1.00 greater than ten percent, almost no successful reconstructions have been observed for any of the three test objects. In addition, we do not a priori know the (non-universal) optimum value for

_{A}*λ*which depends on the object

_{A}*f*

_{in}. Consequently, static overrelaxation does not fulfill the requirements for a good reconstruction algorithm stated above.

*β*= 0.85 without employing overrelaxation by setting the amplitudes

*c*in the operator

_{ξ,n}*Ĥ*

_{HIOR}defined in Eq. (14) equal to

_{R}-algorithm. Clearly, pure randomization without overrelaxation performs equally well as the HIO+O

_{R}-algorithm for all three test objects. However, in our opinion, the HIO+O

_{R}-algorithm should be preferred over randomization without overrelaxation, because (i) it requires only two Fourier transformations for each iteration (lower computational effort) and (ii) it has less degrees of freedom (one uniform random distributions instead of four). Note, however, that due to the large number of degrees of freedom of projection polynomials, further optimization of this approach is possible (including more advanced statistical correlations in the coefficients of the projection polynomial). In addition, more elaborate random distributions might improve both approaches further.

*N*

_{HIO}and

*N*

_{ER}than the traditional HIO+ER-algorithm. Moreover, the (HIO+O

_{R})+ER-algorithm remains almost insensitive to the particular value of the internal parameter

*β*in the range

*β*∈ [0.5, 1.0]. Furthermore, the the good scaling properties in terms of computational time and memory consumption of the HIO+ER-algorithm are fully maintained in the (HIO+O

_{R})+ER-algorithm. In conclusion, a reconstruction based on the (HIO+O

_{R})+ER-algorithm exhibits significantly enhanced stability and success probability in comparison with the traditional and commonly used HIO+ER-algorithm.

## References and links

1. | F. v. d. Veen and F. Pfeiffer, “Coherent x-ray scattering,” Phys J..: Condens. Matter |

2. | R. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A |

3. | U. Pietsch, V. Holy, and T. Baumbach, |

4. | G. N. Afanasiev, |

5. | I. Robinson and R. Harder, “Coherent x-ray diffraction imaging of strain at the nanoscale,” Nat Mater |

6. | J. Miao, P. Charalambous, J. Kirz, and D. Sayre, “Extending the methodology of x-ray crystallography to allow imaging of micrometre-sized non-crystalline specimens,” Nature |

7. | M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature |

8. | A. Biermanns, A. Davydok, H. Paetzelt, A. Diaz, V. Gottschalch, T. H. Metzger, and U. Pietsch, “Individual GaAs nanorods imaged by coherent x-ray diffraction,” J. Synchrotron Radiat. |

9. | A. A. Minkevich, M. Gailhanou, J.-S. Micha, B. Charlet, V. Chamard, and O. Thomas, “Inversion of the diffraction pattern from an inhomogeneously strained crystal using an iterative algorithm,” Phys. Rev. B |

10. | A. A. Minkevich, E. Fohtung, T. Slobodskyy, M. Riotte, D. Grigoriev, T. Metzger, A. C. Irvine, V. Novák, V. Holý, and T. Baumbach, “Strain field in (Ga,Mn)As/GaAs periodic wires revealed by coherent x-ray diffraction,” Europhys. Lett. |

11. | A. A. Minkevich, E. Fohtung, T. Slobodskyy, M. Riotte, D. Grigoriev, M. Schmidbauer, A. C. Irvine, V. Novák, V. Holý, and T. Baumbach, “Selective coherent x-ray diffractive imaging of displacement fields in (Ga,Mn)As/GaAs periodic wires,” Phys. Rev. B |

12. | J. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. |

13. | J. Fienup, “Reconstruction of a complex-valued object from the modulus of its Fourier transform using a support constraint,” J. Opt. Soc. Am. A |

14. | A. Levi and H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A |

15. | D. C. Youla and H. Webb, “Image restoration by the method of convex projections: part 1 – theory,” IEEE Trans. Med. Imaging |

16. | A. A. Minkevich, T. Baumbach, M. Gailhanou, and O. Thomas, “Applicability of an iterative inversion algorithm to the diffraction patterns from inhomogeneously strained crystals,” Phys. Rev. B |

17. | R. P. Millane, “Multidimensional phase problems,” J. Opt. Soc. Am. A |

18. | J. H. Seldin and J. R. Fienup, “Numerical investigation of the uniqueness of phase retrieval,” J. Opt. Soc. Am. A |

19. | R. H. T. Bates, “Fourier phase problems are uniquely solvable in more than one dimension,” Optik (Stuttgart) |

20. | L. Auslander and F. A. Grunbaum, “The Fourier transform and the discrete Fourier transform,” Inverse Prob. |

21. | V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr., Sect. A: Found. Crystallogr. |

22. | J. Miao, D. Sayre, and H. N. Chapman, “Phase retrieval from the magnitude of the Fourier transforms of nonperiodic objects,” J. Opt. Soc. Am. A |

23. | J. Fienup and C. Wackermann, “Phase-retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A |

24. | H. H. Bauschke, P. L. Combettes, and D. R. Luke, “Phase retrieval, error reduction algorithm, and fienup variants: a view from convex optimization,” J. Opt. Soc. Am. A |

25. | H. Takajo, T. Takahashi, R. Ueda, and M. Taninaka, “Study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A |

26. | H. Takajo, T. Takahashi, and T. Shizuma, “Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A |

27. | V. Elser, “Phase retrieval by iterated projections,” J. Opt. Soc. Am. A |

28. | S. Marchesini, “Invited article: A unified evaluation of iterative projection algorithms for phase retrieval,” Rev. Sci. Instrum. |

29. | S. Marchesini, “Phase retrieval and saddle-point optimization,” J. Opt. Soc. Am. A |

**OCIS Codes**

(100.3190) Image processing : Inverse problems

(100.5070) Image processing : Phase retrieval

(290.3200) Scattering : Inverse scattering

(100.3200) Image processing : Inverse scattering

(110.3200) Imaging systems : Inverse scattering

**ToC Category:**

Image Processing

**History**

Original Manuscript: June 18, 2012

Manuscript Accepted: June 25, 2012

Published: July 11, 2012

**Citation**

Martin Köhl, A. A. Minkevich, and Tilo Baumbach, "Improved success rate and stability for phase retrieval by including randomized overrelaxation in the hybrid input output algorithm," Opt. Express **20**, 17093-17106 (2012)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-20-15-17093

Sort: Year | Journal | Reset

### References

- F. v. d. Veen and F. Pfeiffer, “Coherent x-ray scattering,” Phys J..: Condens. Matter16, 5003–5030 (2004). [CrossRef]
- R. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A7, 394–411 (1990). [CrossRef]
- U. Pietsch, V. Holy, and T. Baumbach, High-Resolution X-ray Scattering From Thin Films to Lateral Nanostructures (Springer, New York, 2004).
- G. N. Afanasiev, Vavilov-Cherenkov and Synchrotron Radiation: Foundations and Applications (Springer, Netherlands, 2004).
- I. Robinson and R. Harder, “Coherent x-ray diffraction imaging of strain at the nanoscale,” Nat Mater8, 291–298 (2009). [CrossRef] [PubMed]
- J. Miao, P. Charalambous, J. Kirz, and D. Sayre, “Extending the methodology of x-ray crystallography to allow imaging of micrometre-sized non-crystalline specimens,” Nature400, 342–344 (1999). [CrossRef]
- M. A. Pfeifer, G. J. Williams, I. A. Vartanyants, R. Harder, and I. K. Robinson, “Three-dimensional mapping of a deformation field inside a nanocrystal,” Nature442, 63–66 (2006). [CrossRef] [PubMed]
- A. Biermanns, A. Davydok, H. Paetzelt, A. Diaz, V. Gottschalch, T. H. Metzger, and U. Pietsch, “Individual GaAs nanorods imaged by coherent x-ray diffraction,” J. Synchrotron Radiat.16, 796–802 (2009). [CrossRef] [PubMed]
- A. A. Minkevich, M. Gailhanou, J.-S. Micha, B. Charlet, V. Chamard, and O. Thomas, “Inversion of the diffraction pattern from an inhomogeneously strained crystal using an iterative algorithm,” Phys. Rev. B76, 104106 (2007). [CrossRef]
- A. A. Minkevich, E. Fohtung, T. Slobodskyy, M. Riotte, D. Grigoriev, T. Metzger, A. C. Irvine, V. Novák, V. Holý, and T. Baumbach, “Strain field in (Ga,Mn)As/GaAs periodic wires revealed by coherent x-ray diffraction,” Europhys. Lett.94, 66001 (2011). [CrossRef]
- A. A. Minkevich, E. Fohtung, T. Slobodskyy, M. Riotte, D. Grigoriev, M. Schmidbauer, A. C. Irvine, V. Novák, V. Holý, and T. Baumbach, “Selective coherent x-ray diffractive imaging of displacement fields in (Ga,Mn)As/GaAs periodic wires,” Phys. Rev. B84, 054113 (2011). [CrossRef]
- J. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt.21, 2758–2769 (1982). [CrossRef] [PubMed]
- J. Fienup, “Reconstruction of a complex-valued object from the modulus of its Fourier transform using a support constraint,” J. Opt. Soc. Am. A4, 118–123 (1986). [CrossRef]
- A. Levi and H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A1, 932–943 (1984). [CrossRef]
- D. C. Youla and H. Webb, “Image restoration by the method of convex projections: part 1 – theory,” IEEE Trans. Med. Imaging1, 81 –94 (1982). [CrossRef] [PubMed]
- A. A. Minkevich, T. Baumbach, M. Gailhanou, and O. Thomas, “Applicability of an iterative inversion algorithm to the diffraction patterns from inhomogeneously strained crystals,” Phys. Rev. B78, 174110 (2008). [CrossRef]
- R. P. Millane, “Multidimensional phase problems,” J. Opt. Soc. Am. A13, 725–734 (1996). [CrossRef]
- J. H. Seldin and J. R. Fienup, “Numerical investigation of the uniqueness of phase retrieval,” J. Opt. Soc. Am. A7, 412–427 (1990). [CrossRef]
- R. H. T. Bates, “Fourier phase problems are uniquely solvable in more than one dimension,” Optik (Stuttgart)61, 247–262 (1982).
- L. Auslander and F. A. Grunbaum, “The Fourier transform and the discrete Fourier transform,” Inverse Prob.5, 149 (1989). [CrossRef]
- V. Elser and R. P. Millane, “Reconstruction of an object from its symmetry-averaged diffraction pattern,” Acta Crystallogr., Sect. A: Found. Crystallogr.64, 273–279 (2008). [CrossRef]
- J. Miao, D. Sayre, and H. N. Chapman, “Phase retrieval from the magnitude of the Fourier transforms of nonperiodic objects,” J. Opt. Soc. Am. A15, 1662–1669 (1998). [CrossRef]
- J. Fienup and C. Wackermann, “Phase-retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A3 (1986). [CrossRef]
- H. H. Bauschke, P. L. Combettes, and D. R. Luke, “Phase retrieval, error reduction algorithm, and fienup variants: a view from convex optimization,” J. Opt. Soc. Am. A19, 1334–1345 (2002). [CrossRef]
- H. Takajo, T. Takahashi, R. Ueda, and M. Taninaka, “Study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A15, 2849–2861 (1998). [CrossRef]
- H. Takajo, T. Takahashi, and T. Shizuma, “Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A16, 2163–2168 (1999). [CrossRef]
- V. Elser, “Phase retrieval by iterated projections,” J. Opt. Soc. Am. A20, 40–55 (2003). [CrossRef]
- S. Marchesini, “Invited article: A unified evaluation of iterative projection algorithms for phase retrieval,” Rev. Sci. Instrum.78, 011301 (2007). [CrossRef] [PubMed]
- S. Marchesini, “Phase retrieval and saddle-point optimization,” J. Opt. Soc. Am. A24, 3289–3296 (2007). [CrossRef]

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

« Previous Article | Next Article »

OSA is a member of CrossRef.