PhaseMax
convex relaxation without lifting
-
Phase retrieval deals with the recovery of an \(n\)-dimensional signal \(x^0\in\mathbb{C}^n\), from \(m\geq n\) magnitude measurements of the form \begin{align} \label{eq:original} b_i = |\langle a_i, x^0\rangle|, \quad i = 1,2,\ldots,m, \end{align} where \(a_i\in\mathbb{C}^n\), and \(i=1,2,\ldots,m\) are measurement vectors. While the recovery of \(x^0\) from these non-linear measurements is non-convex, it can be convexified via “lifting” methods that convert the phase retrieval problem to a semidefinite program (SDP). But convexity comes at a high cost: lifting methods square the dimensionality of the problem.
Phasemax achieves convex relaxation without lifting. PhaseMax works by replacing non-convex equality constraints of the form \(|\langle a_i, x^0\rangle|=b_i\) with inequality constraints of the form \(|\langle a_i, x^0\rangle|\le b_i\). Each of these inequality constraints defines a convex set (known as a second-order cone). Next, we choose some approximate “guess” of the true solution, denoted \(\hat x\), and find the vector that lies as far in the direction of \(\hat x\) as possible while still satisfying the inequality constraints. The PhaseMax relaxation is thus
\begin{array}{ll} \tag{PhaseMax} \underset{x\in\mathbb{C}^n}{\text{maximize}} & \qquad \langle x, \hat x \rangle_{\mathbb{R}} \\\ \text{subject to} & \qquad |\langle a_i, x\rangle| \le b_i, \quad i = 1,2,\ldots,m, & \end{array} where \(\langle x, \hat x \rangle_{\mathbb{R}}\) denotes the real part of the (complex) inner product. Despite the simplicity of this relaxation, it is possible to prove that it recovers the true unknown signal with high probability, even when the guess \(\hat x\) is relatively inaccurate or chosen at random. Furthermore, PhaseMax formulations exist that can exploit sparsity and non-negativity, often with stronger recovery guarantees than other methods.
Papers
We are trying to maintain a fairly complete list of papers. Please contact us if you know of related work that should appear below.
Our original work on PhaseMax relaxations
PhaseMax: Convex Phase Retrieval via Basis Pursuit
Goldstein & Studer
An identical formulation was also proposed in…
Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
Bahmani & Romberg
Generalizations of PhaseMax
An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
Hand & Voroninski
Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
Hand & Voroninski
Corruption Robust Phase Retrieval via Linear Programming
Hand & Voroninski
Related non-lifting relaxations for other non-convex problems
BranchHull: Convex bilinear inversion from the entrywise product of signals with known signs
Aghasi, Ahmed, & Hand
Solving Equations of Random Convex Functions via Anchored Regression Authors
Sohail Bahmani, Justin Romberg
New tight performance bounds for non-lifing relaxations
Fundamental Limits of PhaseMax for Phase Retrieval: A Replica Analysis
Oussama Dhifallah & Yue M. Lu
Spectral initialization for nonconvex estimation: High-dimensional limit and phase transitions
Yue Lu & Gen li
Phase Retrieval via Linear Programming: Fundamental Limits and Algorithmic Improvements
Oussama Dhifallah, Christos Thrampoulidis, Yue M. Lu
Code
A solver for the PhaseMax formulation is included (along with many other algorithms) in the general-purpose phase retrieval library PhasePack.
For an example of how to use PhaseMax, see the script runPhasemax.m inside of the examples/ sub-directory of the PhasePack distribution.
Who?
This page is created and maintained by…
Tom Goldstein - University of Maryland
Christoph Studer - Cornell University
How to cite PhaseMax
If you find that our work has contributed to your own, please include the following citation:
@article{goldstein2018phasemax,
title={PhaseMax: Convex phase retrieval via basis pursuit},
author={Goldstein, Tom and Studer, Christoph},
journal={IEEE Transactions on Information Theory},
year={2018}
}
We also strongly encourage authors to cite the work of Bahmani & Romberg, in addition to any relevant works discussed in the Papers section above.
