Solving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns

By E.J. Candes, Xiaodong Li. Foundations of Computational Mathematics, 2012

341 citations recorded by the source corpus.

This note shows that we can recover any complex vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\boldsymbol {x}_{0} \in \mathbb {C}^{n}$\end{document} exactly from on the order of n quadratic equations of the form |〈ai,x0〉|2=bi, i=1,…,m, by using a semidefinite program known as PhaseLift. This improves upon earlier bounds in Candès et al. (Commun. Pure Appl. Math. 66:1241–1274, 2013), which required the number of equations to be at least on the order of nlogn. Further, we show that exact recovery holds for all input vectors simultaneously, and also demonstrate optimal recovery results from noisy quadratic measurements; these results are much sharper than previously known results.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Radiation

View Paper: https://www.semanticscholar.org/paper/6e17b4bae37a557efc2c9826e7fe3b755edfe6bf

How researchers see this paper

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

In Computational Mechanics

In Electrical and Electronic Engineering

In Radiation

Citations in the corpus

Dropping Convexity for Faster Semi-definite Optimization (2015, background): “Specialized algorithms – for objectives beyond the linear case – that utilize such factorization include matrix completion solvers [15], non-negative matrix factorization schemes [19], phase retrieval methods [21, 7, 6] and sparse PCA algorithms [18].”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, neutral): “By dropping the rank constraint, the problem becomes convex [11,16,20,29,113].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “The singleton property assumed in Theorem 35 has been established, for example, for the following two problems: matrix sensing (the positive semidefinite case whereM 0), as long as A satisfies 5r-RIP with a RIP constant δ5r ≤ 1/10 [147]; a necessary and sufficient condition was established in [148];”
Phase Retrieval Using Alternating Minimization (2013, methodology): “, the number of measurements required to recover ) [8], [32].”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, methodology): “2 We see that PhaseMax requires the same sample complexity (number of required measurements) as compared to PhaseLift, TWF, and TAW, when used together with the truncated spectral initializer [17].”
Phase recovery, MaxCut and complex semidefinite programming (2012, background): “If A consists in random Gaussian measurements then uniqueness can be proved, together with stability results [11,13].”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, background): “To alleviate this computational intractability, several convex surrogates have been proposed that work particularly well when the design vectors {ai} are chosen at random [6–20].”
A Geometric Analysis of Phase Retrieval (2016, background): “1): For a fixed problem instance (fixed set of randommeasurements and fixed target x), gradient descent seems to always return a global minimizer (i.e., the target x up to a global phase shift), across many independent random initializations!”
Compressive phase retrieval via generalized approximate message passing (2012, background): “It was then shown in [14] that, with very high probability, PhaseLift recovers (up to a global phase) an arbitrary x0 from m ≥ c0n measurements {y2 i }i=1, where c0 is a sufficiently large constant, when A is i.”
Non-convex Optimization for Machine Learning (2017, neutral): “The phase retrieval problem has been studied extensively in the X-ray crystallography literature where the focus is mostly on studying Fourier measurement matrices [Candès and Li, 2014].”
Phase Retrieval from Coded Diffraction Patterns (2013, neutral): “A subset of the authors [21] reached the same conclusion from on the order of n equations only, by solving the SDP feasibility problem; to be sure, [21] establishes that the set of matrices obeying the constraints in (1. see [27] for a similar result.”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, background): “In comparison, the SDP relaxation only needs a sampling complexity proportional to n (no logarithmic factor) [15], and it is an open question whether Theorem 3.”