A Geometric Analysis of Phase Retrieval

By Ju Sun, Qing Qu, John Wright. International Symposium on Information Theory, 2016

567 citations recorded by the source corpus.

Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of m measurements, $$y_k = \left| \varvec{a}_k^* \varvec{x} \right| $$yk=ak∗x for $$k = 1, \ldots , m$$k=1,…,m, is it possible to recover $$\varvec{x} \in \mathbb C^n$$x∈Cn (i.e., length-n complex vector)? This generalized phase retrieval (GPR) problem is a fundamental task in various disciplines and has been the subject of much recent investigation. Natural nonconvex heuristics often work remarkably well for GPR in practice, but lack clear theoretic explanations. In this paper, we take a step toward bridging this gap. We prove that when the measurement vectors $$\varvec{a}_k$$ak’s are generic (i.i.d. complex Gaussian) and numerous enough ($$m \ge C n \log ^3 n$$m≥Cnlog3n), with high probability, a natural least-squares formulation for GPR has the following benign geometric structure: (1) There are no spurious local minimizers, and all global minimizers are equal to the target signal $$\varvec{x}$$x, up to a global phase, and (2) the objective function has a negative directional curvature around each saddle point. This structure allows a number of iterative optimization methods to efficiently find a global minimizer, without special initialization. To corroborate the claim, we describe and analyze a second-order trust-region algorithm.

Subfields: Atomic and Molecular Physics, and Optics, Computer Vision and Pattern Recognition, Radiation

View Paper: https://www.semanticscholar.org/paper/037dd1f564273b2d9eec19c7f4aa4b879db51ff5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atomic and Molecular Physics, and Optics

In Computer Vision and Pattern Recognition

In Radiation

Citations in the corpus

Global Optimality of Local Search for Low Rank Matrix Recovery (2016, result): “In the past several months, similar type of results were also obtained for other non-convex problems (where the source of non-convexity is not a rank constraint), specifically complete dictionary learning [24] and phase recovery [25].”
Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile (2018, unknown): “, 2015], phase retrieval [Sun et al., 2016], and many other models.”
Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, background): “For instance, Low-rank regression and generalized linear models have been considered by various works including [16,59–62] in such an overdetermined setting.”
Lower bounds for non-convex stochastic optimization (2019, background): “Another growing body of work motivates this study by identifying sub-classes of non-convex problems for which all stationary (or second-order stationary) points are globally optimal [28, 29, 33, 45].”
How to Escape Saddle Points Efficiently (2017, background): “On the other hand, saddle points (and local maxima) can correspond to highly suboptimal solutions in many problems [see, e.g., Jain et al., 2015, Sun et al., 2016b].”
Gradient Descent Converges to Minimizers (2016, background): “Here, by sufficiently small, we simply mean less than the inverse of the Lipschitz constant of the gradient.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “In several problems [40,48,49,75,77,86,87,105,106], it is further suggested that the optimization landscape is benign under sufficiently large sample complexity, in the sense that all local minima are globally optimal, and hence nonconvex iterative algorithms become promising in solving such problem”
Dropping Convexity for Faster Semi-definite Optimization (2015, background): “…includes matrix completion [21, 42, 49, 22], aﬃne rank minimization [65, 41, 8], covariance / inverse covariance selection [38, 50], phase retrieval [64, 18, 77, 68], Euclidean distance matrix completion [56], ﬁnding the square root of a PSD matrix [40], and sparse PCA [26], just to name a few.”
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, background): “For instance, the authors of [50], [51] provide a global analysis of non-convex objectives for phase retrieval and community detection, respectively, ruling out adversarial geometries in these scenarios for the purposes of optimization.”
Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations (2017, unknown): “, see [36, 15, 3, 14, 13, 39] and references therein).”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, background): “For example, it has been proven to be true for objectives of over-parameterized deep networks [16], learning LQR models [19], phase retrieval [54], and many other simple problems discussed in [30].”
Gradient Descent Only Converges to Minimizers (2016, methodology): “We also remark that the authors of Sun et al. (2016) empirically observe gradient descent with 100 random initializations on the phase retrieval problem reliably converges to a local minimizer, and one whose quality matches that of the solution found using more costly trust-region techniques.”
The Power of Normalization: Faster Evasion of Saddle Points (2016, background): “Strict-Saddle-Property: We focus on the optimization of strict-saddle functions, a family of multi-modal functions which encompasses objectives that acquire saddle points.”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, background): “These initializers enable non-convex phase retrieval algorithms to succeed, given a sufficiently large number of measurements; see [36] for more details on the geometry of such non-convex problems.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “This work inspired the line of global geometric analysis for many aforementioned problems, including phase retrieval [28], [90], matrix sensing [31], [32], [143], [153], [154], matrix completion [30], [32], [143], [144], robust PCA [143], M-estimation [155].”