PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming

By E.J. Candes, Thomas Strohmer, Vladislav Voroninski. arXiv.org, 2011

1,383 citations recorded by the source corpus.

Suppose we wish to recover a signal \input amssym $\font\abc=cmmib10\def\bi#1{\hbox{\abc#1}} {\bi x} \in {\Bbb C}^n$ from m intensity measurements of the form $\font\abc=cmmib10\def\bi#1{\hbox{\abc#1}} |\langle \bi x,\bi z_i \rangle|^2$, $i = 1, 2, \ldots, m$; that is, from data in which phase information is missing. We prove that if the vectors $\font\abc=cmmib10\def\bi#1{\hbox{\abc#1}}{\bi z}_i$ are sampled independently and uniformly at random on the unit sphere, then the signal x can be recovered exactly (up to a global phase factor) by solving a convenient semidefinite program–‐a trace‐norm minimization problem; this holds with large probability provided that m is on the order of $n {\log n}$, and without any assumption about the signal whatsoever. This novel result demonstrates that in some instances, the combinatorial phase retrieval problem can be solved by convex programming techniques. Finally, we also prove that our methodology is robust vis‐à‐vis additive noise. © 2012 Wiley Periodicals, Inc.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Radiation

View Paper: https://www.semanticscholar.org/paper/564384c64330d790d6513e869c2bbf2c7bc26fe8

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 Computer Vision and Pattern Recognition

In Radiation

Citations in the corpus

Statistical guarantees for the EM algorithm: From population to sample-based analysis (2014, neutral): “, [3, 9, 35]).”
Phase Retrieval with Application to Optical Imaging: A contemporary overview (2015, methodology): “Alternatively, one may use the log-det reweighted rank minimization heuristic suggested in [97], which is the approach followed in [38] and [46].”
Phase Retrieval Using Alternating Minimization (2013, methodology): “We would like to stress that all the existing guarantees for phase recovery also use exactly the same setting [8], [15], [32].”
Optimal errors and phase transitions in high-dimensional generalized linear models (2017, background): “The free entropy associated with this channel is the expectation of the logarithm of the normalization factor of the associated posterior dP ( x | Y 0 ) that is given by [5] (up to a constant).”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, methodology): “For certain random models, some recent SDP relaxations such as PhaseLift [14] are known to provide exact solutions (up to global phase) to the generalized phase retrieval problem using a near minimal number of sampling vectors [16], [17].”
Solving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns (2012, positive): “Then in all models introduced below, PhaseLift is exact with probability at least 1 − 3 e − γ mn ( γ is a positive numerical constant) in the sense that (1.3) has a unique solution equal to x 0 x ∗ 0 .”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Definition 6) unless the sample size far exceeds the statistical limit; see [45], [47].”
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, methodology): “More broadly, the principled use of sparsity as a prior has led to the development of the field of matrix completion [6], breakthroughs in phase retrieval [7], [8] and blind deconvolution [9]; and is at this point routinely utilized across applied mathematics and machine learning.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, methodology): “Can we reconstruct the underlying object x in a faithful yet efficient manner?Problemsof this kind abound in information and statistical science, prominent examples including low-rank matrix recovery [19,64], robust principal component analysis [17,21], phase retrieval [20,59], neural networks [103,”
A Field Guide to Forward-Backward Splitting with a FASTA Implementation (2014, methodology): “Here, we consider the more recent PhaseLift algorithm, which can be used for phase retrieval applications [27].”
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!”