The problem of phase retrieval is revisited and studied from a fresh perspective. In particular, we establish a connection between the phase retrieval problem and the sensor network localization problem, which allows us to utilize the vast theoretical and algorithmic literature on the latter to tackle the former. Leveraging this connection, we develop a two-stage algorithm for phase retrieval that can provably recover the desired signal. In both sparse and dense settings, our proposed algorithm improves upon prior approaches simultaneously in the number of required measurements for recovery and the reconstruction time. We present numerical results to corroborate our theory and to demonstrate the efficiency of the proposed algorithm. As a side result, we propose a new form of phase retrieval problem and connect it to the complex rigidity theory proposed by Gortler and Thurston.
Over the past few decades, the phase retrieval problem has been extensively studied in the literature. A popular approach in practice is to use the so-called error reduction-type algorithms. Algorithms that fall into this class, including the famous Gerchberg-Saxton algorithm @cite_16 and the Fienup algorithm @cite_14 @cite_6 @cite_28 , are essentially alternating projection-type algorithms @cite_1 . The advantage of this approach is its relatively low computational complexity and flexibility in incorporating prior knowledge of the signal into the recovery process. Unfortunately, this approach often lacks provable convergence guarantees and suffers from the issues of multiple stationary points and instability, especially with non-convex priors @cite_1 . Another weakness is that the number of measurements required when using these algorithms is not known a priori, though some efforts to remedy this have been made in @cite_19 . In particular, @cite_19 studied a version of the alternating projection method for the phase retrieval problem. Their algorithm recovers the signal using @math intensity measurements and has computational complexity @math . However, this is still far from explaining the empirical success of error reduction-type algorithms and a rigorous mathematical foundation for this approach remains elusive.
@cite_14 @cite_28 @cite_1 @cite_6 @cite_19 @cite_16
1972822190 140614008 2007593159 2158746276 1484412996
We present a digital method for solving the phase-retrieval problem of optical-coherence theory: the reconstruction of a general object from the modulus of its Fourier transform. This technique should be useful for obtaining high-resolution imagery from interferometer data. Iterative algorithms for phase retrieval from intensity data are compared to gradient search methods. Both the problem of phase retrieval from two intensity measurements (in electron microscopy or wave front sensing) and the problem of phase retrieval from a single intensity measurement plus a non-negativity constraint (in astronomy) are considered, with emphasis on the latter. It is shown that both the error-reduction algorithm for the problem of a single intensity measurement and the Gerchberg-Saxton algorithm for the problem of two intensity measurements converge. The error-reduction algorithm is also shown to be closely related to the steepest-descent method. Other algorithms, including the input–output algorithm and the conjugate-gradient method, are shown to converge in practice much faster than the error-reduction algorithm. Examples are shown. Phase retrieval problems involve solving linear equations, but with missing sign (or phase, for complex numbers) information. More than four decades after it was first proposed, the seminal error reduction algorithm of (Gerchberg and Saxton 1972) and (Fienup 1982) is still the popular choice for solving many variants of this problem. The algorithm is based on alternating minimization; i.e. it alternates between estimating the missing phase information, and the candidate solution. Despite its wide usage in practice, no global convergence guarantees for this algorithm are known. In this paper, we show that a (resampling) variant of this approach converges geometrically to the solution of one such problem -- finding a vector @math from @math , where @math and @math denotes a vector of element-wise magnitudes of @math -- under the assumption that @math is Gaussian. Empirically, we demonstrate that alternating minimization performs similar to recently proposed convex techniques for this problem (which are based on "lifting" to a convex matrix problem) in sample complexity and robustness to noise. However, it is much more efficient and can scale to large problems. Analytically, for a resampling version of alternating minimization, we show geometric convergence to the solution, and sample complexity that is off by log factors from obvious lower bounds. We also establish close to optimal scaling for the case when the unknown vector is sparse. Our work represents the first theoretical guarantee for alternating minimization (albeit with resampling) for any variant of phase retrieval problems in the non-convex setting. An algorithm is presented for the rapid solution of the phase of the complete wave function whose intensity in the diffraction and imaging planes of an imaging system are known. A proof is given showing that a defined error between the estimated function and the correct function must decrease as the algorithm iterates. The problem of uniqueness is discussed and results are presented demonstrating the power of the method.