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

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

Corruption Robust Phase Retrieval via Linear Programming
Hand & Voroninski

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

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.

The PhasePack library

For an example of how to use PhaseMax, see the script runPhasemax.m inside of the examples/ sub-directory of the PhasePack distribution.

Who?

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.