Hybrid input output (HIO) algorithm for phase retrieval
Encyclopedia
Hybrid input-output algorithm for phase retrieval is a modification of the error reduction algorithm for retrieving the phases in Coherent diffraction imaging
. Determining the phases of a diffraction pattern is crucial since the diffraction pattern of an object is its Fourier transform
and in order to properly inverse transform the diffraction pattern the phases must be known. The amplitude however, can be measured from the intensity of the diffraction pattern and can thus be known experimentally. This fact together with some kind of support (mathematics)
can be used in order to iteratively calculate the phases. The HIO algorithm uses negative feedback in fourier space in order to progressively force the solution to conform to the fourier domain constraints (support). Unlike the error reduction algorithm which alternately applies fourier and object constraints the HIO "skips" the object domain step and replaces it with negative feedback acting upon the previous solution.
Although it has been shown that the method of error reduction converges to a limit (but usually not to the correct or optimal solution)
there is no limit to how long this process can take. Moreover, the error reduction algorithm will almost certainly find a local minima instead of the global. The HIO differs from error reduction only in one step but this is enough to reduce this problem significantly. Whereas the error reduction approach iteratively improves solutions over time the HIO remodels the previous solution in Fourier space applying negative feedback. By minimizing the mean square error in the Fourier space from the previous solution, the HIO provides a better candidate solution for inverse transforming. Although being both faster and more powerful, the HIO does have a uniqueness problem.
Depending on how strong the negative feedback is there can more often be more than one solution for any set of diffraction data. This might seem like a big problem but it has been shown that many of these possible solutions stem from the fact that HIO allows for mirror images taken in any plane to arise as solutions. In crystallography, the scientist is seldom interested in the atomic coordinates relative to any other reference than the molecule itself and is therefore more than happy with a solution that is upside-down of flipped from the actual image. On the downside, HIO does have a tendency to be able to escape both global and local maxima. This is probably also depending on the strength of the feedback parameter and a good solution to this problem is to switch algorithm when the error reaches its minimum. Other methods of phasing a coherent diffraction pattern include difference map algorithm
and "relaxed averaged alternating reflections" or RAAR.
Coherent diffraction imaging
Coherent diffractive imaging also coherent diffracton imaging is a “lensless” technique for 2D or 3D reconstruction of the image of nanoscale structures such as nanotubes1, nanocrystals², defects³, potentially proteins4 and more4. In CDI, a highly coherent beam of x-rays, electrons or other...
. Determining the phases of a diffraction pattern is crucial since the diffraction pattern of an object is its Fourier transform
Fourier transform
In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
and in order to properly inverse transform the diffraction pattern the phases must be known. The amplitude however, can be measured from the intensity of the diffraction pattern and can thus be known experimentally. This fact together with some kind of support (mathematics)
Support (mathematics)
In mathematics, the support of a function is the set of points where the function is not zero, or the closure of that set . This concept is used very widely in mathematical analysis...
can be used in order to iteratively calculate the phases. The HIO algorithm uses negative feedback in fourier space in order to progressively force the solution to conform to the fourier domain constraints (support). Unlike the error reduction algorithm which alternately applies fourier and object constraints the HIO "skips" the object domain step and replaces it with negative feedback acting upon the previous solution.
Although it has been shown that the method of error reduction converges to a limit (but usually not to the correct or optimal solution)
there is no limit to how long this process can take. Moreover, the error reduction algorithm will almost certainly find a local minima instead of the global. The HIO differs from error reduction only in one step but this is enough to reduce this problem significantly. Whereas the error reduction approach iteratively improves solutions over time the HIO remodels the previous solution in Fourier space applying negative feedback. By minimizing the mean square error in the Fourier space from the previous solution, the HIO provides a better candidate solution for inverse transforming. Although being both faster and more powerful, the HIO does have a uniqueness problem.
Depending on how strong the negative feedback is there can more often be more than one solution for any set of diffraction data. This might seem like a big problem but it has been shown that many of these possible solutions stem from the fact that HIO allows for mirror images taken in any plane to arise as solutions. In crystallography, the scientist is seldom interested in the atomic coordinates relative to any other reference than the molecule itself and is therefore more than happy with a solution that is upside-down of flipped from the actual image. On the downside, HIO does have a tendency to be able to escape both global and local maxima. This is probably also depending on the strength of the feedback parameter and a good solution to this problem is to switch algorithm when the error reaches its minimum. Other methods of phasing a coherent diffraction pattern include difference map algorithm
Difference map algorithm
The difference-map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta-algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets. From a mathematical perspective, the difference-map algorithm is a...
and "relaxed averaged alternating reflections" or RAAR.