Algorithmic determination of wave cycle parts
Phase retrieval is the process of algorithmically finding solutions to the phase problem. Given a complex spectrum formula_1, of amplitude formula_2, and phase formula_3:
formula_4
where "x" is an "M"-dimensional spatial coordinate and "k" is an "M"-dimensional spatial frequency coordinate. Phase retrieval consists of finding the phase that satisfies a set of constraints for a measured amplitude. Important applications of phase retrieval include X-ray crystallography, transmission electron microscopy and coherent diffractive imaging, for which formula_5. Uniqueness theorems for both 1-D and 2-D cases of the phase retrieval problem, including the phaseless 1-D inverse scattering problem, were proven by Klibanov and his collaborators (see References).
Problem formulation.
Here we consider 1-D discrete Fourier transform (DFT) phase retrieval problem. The DFT of a complex signal formula_6 is given by 
formula_7,
and the oversampled DFT of formula_8 is given by 
formula_9,
where formula_10.
Since the DFT operator is bijective, this is equivalent to recovering the phase formula_11. It is common recovering a signal from its autocorrelation sequence instead of its Fourier magnitude. That is, denote by formula_12 the vector formula_13 after padding with formula_14 zeros. The autocorrelation sequence of formula_12 is then defined as
formula_16,
and the DFT of formula_17, denoted by formula_18, satisfies formula_19.
Methods.
Error reduction algorithm.
The error reduction is a generalization of the Gerchberg–Saxton algorithm. It solves for formula_20 from measurements of formula_21 by iterating a four-step process. For the formula_22th iteration the steps are as follows:
Step (1): formula_23, formula_24, and formula_25 are estimates of, respectively, formula_26, formula_27 and formula_20. In the first step we calculate the Fourier transform of formula_25:
formula_30
Step (2): The experimental value of formula_21, calculated from the diffraction pattern via the signal equation, is then substituted for formula_32, giving an estimate of the Fourier transform:
formula_33
where the ' denotes an intermediate result that will be discarded later on.
Step (3): the estimate of the Fourier transform formula_34 is then inverse Fourier transformed:
formula_35
Step (4): formula_36 then must be changed so that the new estimate of the object, formula_37, satisfies the object constraints. formula_37 is therefore defined piecewise as:
formula_39
where formula_40 is the domain in which formula_36 does not satisfy the object constraints. A new estimate formula_37 is obtained and the four step process is repeated.
This process is continued until both the Fourier constraint and object constraint are satisfied. Theoretically, the process will always lead to a convergence, but the large number of iterations needed to produce a satisfactory image (generally ;2000) results in the error-reduction algorithm by itself being unsuitable for practical applications.
Hybrid input-output algorithm.
The hybrid input-output algorithm is a modification of the error-reduction algorithm - the first three stages are identical. However, formula_25 no longer acts as an estimate of formula_20, but the input function corresponding to the output function formula_36, which is an estimate of formula_20. In the fourth step, when the function formula_36 violates the object constraints, the value of formula_48 is forced towards zero, but optimally not to zero. The chief advantage of the hybrid input-output algorithm is that the function formula_25 contains feedback information concerning previous iterations, reducing the probability of stagnation. It has been shown that the hybrid input-output algorithm converges to a solution significantly faster than the error reduction algorithm. Its convergence rate can be further improved through step size optimization algorithms.
formula_50
Shrinkwrap.
For a two dimensional phase retrieval problem, there is a degeneracy of solutions as formula_20 and its conjugate formula_54 have the same Fourier modulus. This leads to "image twinning" in which the phase retrieval algorithm stagnates producing an image with features of both the object and its conjugate. The shrinkwrap technique periodically updates the estimate of the support by low-pass filtering the current estimate of the object amplitude (by convolution with a Gaussian) and applying a threshold, leading to a reduction in the image ambiguity.
Semidefinite relaxation-based algorithm for short time Fourier transform.
The phase retrieval is an ill-posed problem. To uniquely identify the underlying signal, in addition to the methods that adds additional prior information like Gerchberg–Saxton algorithm, the other way is to add magnitude-only measurements like short time Fourier transform (STFT).
The method introduced below mainly based on the work of Jaganathan "et al".
Short time Fourier transform.
Given a discrete signal formula_55 which is sampled from formula_56. We use a window of length "W": formula_57 to compute the STFT of formula_58, denoted by formula_59:
formula_60
for formula_61 and formula_62, where the parameter formula_63 denotes the separation in time between adjacent short-time sections and the parameter formula_64 denotes the number of short-time sections considered.
The other interpretation (called sliding window interpretation) of STFT can be used with the help of discrete Fourier transform (DFT). Let formula_65 denotes the window element obtained from shifted and flipped window formula_66. Then we have
formula_67, where formula_68.
Problem definition.
Let formula_69 be the formula_70 measurements corresponding to the magnitude-square of the STFT of formula_71, formula_72 be the formula_73 diagonal matrix with diagonal elements formula_74 STFT phase retrieval can be stated as: 
Find formula_71 such that formula_76 for formula_77 and formula_78, where formula_79 is the formula_80-th column of the formula_81-point inverse DFT matrix. 
Intuitively, the computational complexity growing with formula_81 makes the method impractical. In fact, however, for the most cases in practical we only need to consider the measurements corresponding to formula_83, for any parameter formula_84 satisfying formula_85. 
To be more specifically, if both the signal and the window are not "vanishing", that is, formula_86 for all formula_87 and formula_88 for all formula_89 formula_90, signal formula_71 can be uniquely identified from its STFT magnitude if the following requirements are satisfied: 
The proof can be found in Jaganathan' s work, which reformulates STFT phase retrieval as the following least-squares problem:
formula_94.
The algorithm, although without theoretical recovery guarantees, empirically able to converge to the global minimum when there is substantial overlap between adjacent short-time sections.
Semidefinite relaxation-based algorithm.
To establish recovery guarantees, one way is to formulate the problems as a semidefinite program (SDP), by embedding the problem in a higher dimensional space using the transformation formula_95 and relax the rank-one constraint to obtain a convex program. The problem reformulated is stated below:
Obtain formula_96 by solving:formula_97for formula_98 and formula_78
Once formula_96 is found, we can recover signal formula_71 by best rank-one approximation.
Applications.
Phase retrieval is a key component of coherent diffraction imaging (CDI). In CDI, the intensity of the diffraction pattern scattered from a target is measured. The phase of the diffraction pattern is then obtained using phase retrieval algorithms and an image of the target is constructed. In this way, phase retrieval allows for the conversion of a diffraction pattern into an image without an optical lens.
Using phase retrieval algorithms, it is possible to characterize complex optical systems and their aberrations. For example, phase retrieval was used to diagnose and repair the flawed optics of the Hubble Space Telescope.
Other applications of phase retrieval include X-ray crystallography and transmission electron microscopy.
References.
 ;templatestyles src="Reflist/styles.css" / ;