Phase Retrieval via Wirtinger Flow: Theory and Algorithms
By E.J. Candes, Xiaodong Li, M. Soltanolkotabi. 2014
1,398 citations recorded by the source corpus.
We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal x ∈ ℂn about which we have phaseless samples of the form yr = |〈ar, x〉|2, r = 1, ..., m (knowledge of the phase of these samples would yield a linear system). This paper develops a nonconvex formulation of the phase retrieval problem as well as a concrete solution algorithm. In a nutshell, this algorithm starts with a careful initialization obtained by means of a spectral method, and then refines this initial estimate by iteratively applying novel update rules, which have low computational complexity, much like in a gradient descent scheme. The main contribution is that this algorithm is shown to rigorously allow the exact retrieval of phase information from a nearly minimal number of random measurements. Indeed, the sequence of successive iterates provably converges to the solution at a geometric rate so that the proposed scheme is efficient both in terms of computational and data resources. In theory, a variation on this scheme leads to a near-linear time algorithm for a physically realizable model based on coded diffraction patterns. We illustrate the effectiveness of our methods with various experiments on image data. Underlying our analysis are insights for the analysis of nonconvex optimization schemes that may have implications for computational problems beyond phase retrieval.
Subfields: Computer Vision and Pattern Recognition, Radiation, Structural Biology, Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Ming-Hsuan Yang
- Trevor Darrell
- Xiaogang Wang
- Yi Yang
- Jitendra Malik
- Andrew Zisserman
In Radiation
- Yuxin Chen
- Tom Goldstein
- Christoph Studer
- Yuejie Chi
- E.J. Candes
- Yonina C. Eldar
- Prateek Jain
- M. Soltanolkotabi
In Structural Biology
- Yuxin Chen
- Yuejie Chi
- Christoph Studer
- Tom Goldstein
- Ganzhao Yuan
- Bernard Ghanem
- Sujay Sanghavi
- Prateek Jain
In Optimization & Training
- Jason D. Lee
- Michael I. Jordan
- Yuejie Chi
- Yuxin Chen
- Praneeth Netrapalli
- Yonina C. Eldar
- Peter L. Bartlett
- Yue M. Lu
Citations in the corpus
- Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “Finally, we state a Lemma based on [11], [43], and [45] that allows us to lower bound the loss function L(v,W) in terms of how close (v,W) is to (v∗,W∗).”
- Gradient Descent Converges to Minimizers (2016, background): “We remark that the strict saddle assumption is necessary in the worst case, due to hardness results regarding testing the local optimality of functions whose Hessians are highly degenerate at criticalpoints (e.g, quartic polynomials) [19].”
- Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions (2016, background): “dictionary learning [1], latent-variable models [28], matrix completion [9], and phase retrieval [2]).”
- An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, background): “Recent work in [25] shows that a local descent algorithm again coupled with a smart initialization is as effective for phase retrieval as the convex relaxations above while being far more computationally efficient.”
- Phase Retrieval Using Alternating Minimization (2013, methodology): “We also define Ph ( z ) for every w 1 , w 2 ∈ C n . inally, we use the shorthand wlog for without loss of generality and whp for with high probability.”
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow (2016, methodology): “Specifically, our initialization is built upon the hidden orthogonality characteristics of high-dimensional random vectors [53], which is in stark contrast to spectral alternatives starting from the strong law of large numbers (SLLN) [15], [30], [7].”
- Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, background): “Additionally, rigorous guarantees of nonconvex recovery include other results in phase retrieval [52], [53], blind deconvolution [54]–[56], robust subspace recovery [57], discrete joint alignment [58], and more.”
- Learning ReLUs via Gradient Descent (2017, neutral): “These results are mostly adapted from [17, 2, 16].”
- Dropping Convexity for Faster Semi-definite Optimization (2015, background): “Thus, a scaling of P + ( f (0)) by M could serve as a decent initialization. initialization −∇ In many recent works [42, 64, 19, 82, 23] this has been used for specific applications.”
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “[102] used this method to address the problem of phase retrieval, the theoretical guarantee of which was tightened in [19].”
- An Exact Penalty Method for Binary Optimization Based on MPEC Formulation (2017, methodology): “…work of (Zhang, 2010) considers a multi-stage convex optimization algorithm to refine the global solution by the initial convex method; the work of (Candès, Li, and Soltanolkotabi, 2015) starts with a careful initialization obtained by a spectral method and improves this estimate by gradient…”
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, background): “(26) Loop: for t = 0 : T do z(t+1) = z(t) + 2µt m m∑ i=1 yi − ∣∣a∗i z(t)∣∣2 z(t)∗ai ai1Ei1∩Ei2 , (27) where E i1 := { αlbz ≤ √ n ‖ai‖ |a∗i z(t)| ‖z(t)‖ ≤ α ub z } , E i2 := { |yi − |a∗i z(t)|2| ≤ αhKt √ n ‖ai‖ |a∗i z(t)| ‖z(t)‖ } , (28) and Kt := 1 m m∑ l=1 ∣∣yl − |a∗l z(t)|2∣∣.”
- Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking (2017, neutral): “…methods has been successfully applied in numerous applications, e.g. matrix completion (Keshavan et al., 2010; Jain et al., 2013), phase retrieval (Candès et al., 2015; Chen and Candès, 2017), graph clustering (Rohe et al., 2011; Chaudhuri et al., 2012), synchronization and joint alignment…”