# 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.