A Precise Analysis of PhaseMax in Phase Retrieval

I Introduction

The fundamental problem of recovering a signal from magnitude-only measurements is known as phase retrieval. This problem has a rich history and occurs in many areas in engineering and applied physics such as astronomical imaging , X-ray crystallography , medical imaging , and optics . In most of these cases, measuring the phase is either expensive or even infeasible. For instance, in some optical settings, detection devices like CCD cameras and photosensitive films cannot measure the phase of a light wave and instead measure the photon flux.

Reconstructing a signal from magnitude-only measurements is generally very difficult due to loss of important phase information. Therefore, phase retrieval faces fundamental theoretical and algorithmic challenges and a variety of methods were suggested . Convex methods have recently gained significant attention to solve the phase retrieval problem. These methods are mainly based on semidefinite programming by linearizing the resulting quadratic constraints using the idea of lifting . Due to the convex nature of their formulation, these algorithms usually have rigorous theoretical guarantees. However, semidefinite relaxation squares the number of unknowns which makes these algorithms computationally complex, especially in large systems. This caveat makes these approaches intractable in real-world applications.

Introduced in two independent works , PhaseMax is a recently proposed convex formulation for the phase retrieval problem in the original $n-$dimensional parameter space. This method maximizes a linear functional over a convex feasible set. The constrained set in this optimization is obtained by relaxing the non-convex equality constraints in the original phase retrieval problem to convex inequality constraints. To form the objective function, PhaseMax relies on an initial estimate of the true signal which must be externally provided.

The simple formulation of the PhaseMax method makes it appealing for practical applications. In addition, existing theoretical analysis indicates this method achieves perfect recovery for a nearly optimal number of random measurements. The analysis in suggests that $m>Cn$, where $C$ is a constant that depends on the quality of initial estimate ($\mathbf{x}_{\text{init}}$), is the sufficient number of measurements for perfect signal reconstruction when the measurement vectors are drawn independently from the Gaussian distribution. The exact phase transition threshold, i.e. the exact value of the constant $C$, for the real PhaseMax has been recently derived in . However, for the practical case of complex signals, previous results could only provide an upper bound on $C$.

In this paper, we characterize the phase transition regimes for the perfect signal recovery in the PhaseMax algorithm. Our result is asymptotic and assumes that the measurement vectors are derived independently from Gaussian distribution. To the extent of our knowledge, this is the first work that computes the exact phase transition bound of the (complex-valued) PhaseMax in phase retrieval.

In our analysis, we utilize the recently developed Convex Gaussian Min-max Theorem (CGMT) which uses Gaussian process methods. CGMT has been successfully applied in a number of different problems including the performance analysis of structured signal recovery in M-estimators , massive MIMO and etc. CGMT has been also used by Dhifallah et. al. to analyze the real version of the PhaseMax. But unfortunately, the complex case does not directly fit into the framework of CGMT. Therefore, in this paper we introduce a secondary optimization that provably has the same phase transition bounds as PhaseMax and that also can be analyzed by CGMT.

The organization of the paper is as follows. In section II we introduce the main notations and mathematically setup the problem. In section III, we present our main result followed by discussions and the result of numerical simulations. Finally, section IV includes an outline of the proof of the main theorem.

II Problem Setup

II-B Setup

This optimization searches for a feasible vector that posses the most real correlation with $\mathbf{x}_{\text{init}}$. Note that because of the global phase ambiguity of the measurements in (1), we can estimate $\mathbf{x}_{0}$ up to a global phase. Therefore, we define the following performance measure for the PhaseMax method,

Under this setting, a perfect recovery of $\mathbf{x}_{0}$ means $\mathbf{D}(\hat{\mathbf{x}},\mathbf{x}_{0})=0$. In this paper we investigate the necessary and sufficient conditions under which the optimization program (2) perfectly recovers the true signal.

III Main Result

In this section, we present the main result of the paper which provides us with the necessary and sufficient number of measurements for the perfect recovery of the PhaseMax method in (2) under different scenarios. Our result is asymptotic which assumes a fixed oversampling ratio $\delta:=\frac{m}{n}\in[0,\infty)$, while $n\rightarrow\infty$. In theorem III.1, we introduce $\delta_{\text{rec}}$ which depends on the problem parameters and prove that the condition $\delta>\delta_{\text{rec}}$, is necessary and sufficient for perfect recovery. Our result reveals significant dependence between $\delta_{\text{rec}}$ and the quality of the initial guess. We use the following similarity measure to quantify the caliber of the initial estimate:

Note that the multiplication by a unit amplitude scalar in the above definition is due to the global phase ambiguity of the phase retrieval solution (the true phase of $\mathbf{x}_{0}$ is dissolved in the absolute value in (1)). Therefore, for convenience we assume both $\mathbf{x}_{\text{init}}$ and $\mathbf{x}_{0}$ are aligned unit norm vectors ($||\mathbf{x}_{0}||=||\mathbf{x}_{\text{init}}||=1$), which results in $\rho_{\text{init}}=\mathbf{x}_{\text{init}}^{\star}\;\mathbf{x}_{0}$. We also define $\theta$ as the angle between $\mathbf{x}_{\text{init}}$ and $\mathbf{x}_{0}$, and therefore, $\rho_{\text{init}}=\cos\theta$. We now present the main result of the paper which characterizes the phase transition regimes of PhaseMax for perfect recovery, in terms of $\delta$ and $\rho_{\text{init}}$.

where $\rho_{\text{init}}$ is defined in (4).

Theorem III.1 establishes a sharp phase transition behavior for the performance of PhaseMax. The inequality (5) can also be rewritten in terms of $\theta$ (or $\rho_{\text{init}}$) when the oversampling ratio, $\delta$, is fixed,

The proof of Theorem III.1 consists of two main steps. First, we introduce a real optimization program with $2n-1$ variables and prove that it has the same phase transition bounds as PhaseMax in (2). The point of this step is that this new real optimization is especially built in a way that its performance can be precisely analyzed using well known tools like CGMT. Therefore, the next step would be to apply the CGMT framework to the new real optimization and to derive its phase transition bounds. We postpone a detailed version of the proof to section IV.

The condition $\delta>4$ is proven to be fundamentally necessary for the phase retrieval problem under generic measurements to have a unique solution . This is consistent with Theorem III.1 where you can observe that even in the best scenario where $\mathbf{x}_{\text{init}}$ is aligned with $\mathbf{x}_{0}$, we still need $m>4n$ measurements for PhaseMax to have $\mathbf{x}_{0}$ as the solution. On the other hand, in the case where $\mathbf{x}_{\text{init}}$ carries no information about $\mathbf{x}_{0}$ ($\mathbf{x}_{\text{init}}$ is orthogonal to $\mathbf{x}_{0}$), recovery of $\mathbf{x}_{0}$ by PhaseMax is not guaranteed regardless of the number of measurements.

It is shown in the work of Goldstein et. al. that $\delta>\frac{4}{1-2\theta/\pi}$ is sufficient for perfect recovery of $\mathbf{x}_{0}$. This bound is compared to our result in Fig. 1 which shows phase transition regions of PhaseMax derived from empirical results. Although the simulations are run on the signals of size $n=128$, one can see that the blue line that comes from Theorem III.1, perfectly predicts phase transition boundary.

IV Proof Outline

In the second step, we adopt the CGMT framework to analyze the ERO and investigate the conditions on $\rho_{\text{init}}$ (or $\theta$) under which the unique answer to the ERO is $\mathbf{0}$. Therefore ,as a result of Lemma IV.4, these conditions will guarantee the perfect recovery in the initial PhaseMax optimization (2).

We define the error vector $\mathbf{w}:=\mathbf{x}-\mathbf{x}_{0}$ and rewrite (2) in terms of $\mathbf{w}$,

$\mathbf{x}_{0}$ is the unique optimal solution of (2) if and only if $\mathcal{D}\bigcap\mathcal{F}=\{\mathbf{0}\}$.

For $\mathbf{w}\in\mathcal{D}\bigcap\mathcal{F}$, $\mathbf{x}_{0}+\mathbf{w}$ is a solution of (2) with an objective value greater than the value for $\mathbf{x}_{0}$. Therefore, $\mathcal{D}\bigcap\mathcal{F}=\{\mathbf{0}\}$ is equivalent to $\mathbf{x}_{0}$ be a local minimum of (2) which is also a global minimum due to convexity of (2). ∎

$\mathcal{D}\bigcap\mathcal{F}=\{\mathbf{0}\}$ if and only if $\mathcal{D}\bigcap\text{cone}(\mathcal{F})=\{\mathbf{0}\}$.

We have the following corollary as a result of Lemma IV.1, Lemma IV.2, and Lemma IV.3.

$\mathbf{x}_{0}$ is the unique optimal solution of (2) if and only if,

We are now ready to establish the equivalent real optimization ERO. We will show that the ERO has the exact phase transition bounds as PhaseMax in (2).

$\mathbf{x}_{0}$ is the unique optimal solution of the PhaseMax method if and only if $\mathbf{w}^{\prime}=0$ is the unique optimal solution of (12).

The proof of Lemma IV.4 is straightforward by defining

and then showing that the optimality conditions for $\mathbf{w}^{\prime}=0$ in (12) is equivalent to (11).

It is worth mentioning that the result of Lemma IV.4 is valid for any set of measurement vectors $\{\mathbf{a}_{i}\}$. In the next part, we use this result to compute the phase transition of PhaseMax when the measurement vectors are drawn independently from the Gaussian distribution.

IV-B Convex Gaussian Min-Max Theorem

Our analysis is based on the recently developed Convex Gaussian Min-max Theorem (CGMT) . The CGMT associates with a Primary Optimization (PO) problem an Auxiliary Optimization (AO) problem from which we can investigate various properties of the primary optimization, such as phase transitions. In particular, the (PO) and the (AO) problems are defined respectively as follows:

Consider the two optimizations (15a) and (15b). Let ${\mathbf{S}}_{\mathbf{w}},{\mathbf{S}}_{\mathbf{u}}$ be convex and compact sets, $\psi$ be continuous and convex-concave on ${\mathbf{S}}_{\mathbf{w}}\times{\mathbf{S}}_{\mathbf{u}}$, and, $\mathbf{G},\mathbf{g}$ and $\mathbf{h}$ all have entries iid standard normal. Suppose there exist ${\alpha}$ such that in the limit of $n\rightarrow\infty$ it holds in probability that $\|\mathbf{w}_{\phi}(\mathbf{g},\mathbf{h})\|\rightarrow{\alpha}$. Then, the same holds for $\mathbf{w}_{\Phi}(\mathbf{G})$ and we have $\|\mathbf{w}_{\Phi}(\mathbf{G})\|\rightarrow{\alpha}$.

In the next section, first we will rewrite the ERO in the form of the optimization (15a). This enables us to apply Lemma IV.5 to the ERO and derive an Auxiliary Optimization in the form of (15b). This lemma indicates that if $\|\mathbf{w}_{\phi}(\mathbf{g},\mathbf{h})\|\rightarrow 0$ for the (AO), then $\|\mathbf{w}_{\Phi}(\mathbf{G})\|\rightarrow 0$ for the ERO and we have perfect recovery. (AO) can be analyzed using the conventional concentration results in high dimensions.

IV-C Computing the Phase Transition for PhaseMax

In this part we adopt the CGMT framework along with the result of Lemma IV.4 to compute the exact phase transition of the PhaseMax algorithm under the Gaussian measurement scheme.

In the asymptotic regime where $m,n\rightarrow\infty$, and $\delta:=\frac{m}{n}$, $s^{*}$ and $t^{*}$ converges to the solution of the following deterministic optimization,

In the above optimization, $p(t,s)$ is define as,

It can be shown that $\rho_{\text{init}}>\frac{2}{\sqrt{\delta}}$ is the necessary and sufficient condition for $(t^{*},s^{*})=(0,1)$ to be the unique solution of (21) which is equivalent to the perfect recovery in the ERO.

V Acknowledgment

This work was inspired by the ideas presented in . The authors would like to thank Yue M. Lu, Christos Thrampoulidis, and Philipp Walk for helpful discussions.

References