An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax

Introduction

To the surprise of the community, a recent successful formulation for phase retrieval called PhaseMax, independently developed in , is convex and operates in the natural $n$-dimensional parameter space. The theoretical results of achieve a tighter sample complexity than those in , notably providing guarantees very close to the information theoretic lower-bounds. Both of these approaches rely on first finding an anchor vector which is positively correlated with the vector $x_{0}$, provided for instance by using a spectral initialization first reported on by Netrapali et al. and further enhanced by authors of Wirtinger Flow-like methods. The proof in uses arguments based on statistical learning theory, and the the proof in uses arguments from sphere covering and geometric probability.

In this short paper, we consider only the real-valued case for simplicity (the complex case is very similar) and present an alternate elementary proof that PhaseMax succeeds in finding $x_{0}$ up to global sign from $O(n)$ phaseless Gaussian measurements, thus achieving phase retrieval under optimal sample complexity via a linear program with a linear number of constraints. Our proof is based on standard elementary probabilistic concentration estimates of the singular values of random matrices.

Main Result and Proof

Here, $\gamma$ and $c$ are universal constants.

A satisfactory anchor vector can be efficiently computed with high probability by several methods. For concreteness, consider the truncated spectral initializer in . With $\lambda=\sqrt{\frac{1}{m}\sum_{i=1}^{m}y_{i}^{2}}$, let

By Proposition 3 from , for a fixed $x_{0}$, this truncated spectral initializer satisfies $\min(\|\phi-x_{0}\|,\|\phi+x_{0}\|)\leq 0.6\|x_{0}\|_{2}$ with probability at least $1-e^{-\gamma m}$, provided that $m\geq c_{0}n$. Note that in the case where $\|\phi+x_{0}\|\leq 0.6\|x_{0}\|_{2}$, then the output of PhaseMax will be $-x_{0}$ with high probability, which is exact up to the inherent global phase ambiguity. Alternatively, one could use the leading eigenvector of $\frac{1}{m}\sum_{i=1}^{m}y_{i}^{2}a_{i}a_{i}^{\intercal}$ as the anchor vector, as done in the initialization steps of AltMinPhase and Wirtinger Flow . In this case $m=O(n\log n)$ measurements are necessary to obtain an accurate anchor vector . The initialization from the Truncated Amplitude Flow could also be used under $m=O(n)$.

Proof

Throughout the proof, the values of constants $c$ and $\gamma$ may change line to line, but they are bounded from above and below by fixed positive numbers. The proof uses a technical lemma that bounds the singular values of $\frac{1}{m}\sum_{i=1}^{m}a_{i}a_{i}^{\intercal}$ and a technical lemma that bounds $\frac{1}{m}\sum_{i=1}^{m}|\langle a_{i},x_{0}\rangle||\langle a_{i},x_{1}\rangle|$ from below with high probability.

Suppose $\langle a_{i},h\rangle\langle a_{i},x_{0}\rangle\leq 0$ for all $i$. Then,

By Lemma 2, if $m\geq\epsilon^{-2}n$, then on an event of probability at least $1-2e^{-\gamma\epsilon^{2}m}$,

By Lemma 3The same result holds with the constant $0.45$ by applying Lemma 3.2 from PhaseLift to $hx_{0}^{\intercal}+x_{0}h^{\intercal}$., if $m\geq c_{0}n$, then on an event of probability at least $1-4e^{-\gamma m}$,

Finally, for nonzero $h$, we use the assumption that $\|\phi-x_{0}\|_{2}<0.6\|x_{0}\|_{2}$ to conclude

on an event of probability at least $1-6e^{-\gamma m}$. ∎

This claim follows from standard concentration estimates for Gaussian matrices (e.g. Corollary 5.35 in ). ∎

There exist constants $c_{0},\gamma,\delta_{0}$ such that for any $0<\delta<\delta_{0}$, if $m\geq c_{0}(\delta^{-2}\log\delta^{-1})n$, then with probability at least $1-4e^{-\gamma m\delta^{2}}$

Choose $\delta_{1}=\delta/\pi,\delta_{2}=1/2,\epsilon=2\delta/(9\pi)$. Further, choose $\delta_{0}$ such that $\delta_{1}<K$. Thus, on $E_{1}\cap E_{2}$, $\frac{1}{m}\|\mathcal{A}(x_{0}x_{1}^{\intercal})\|_{1}\geq\frac{2}{\pi}(1-\delta)$. It remains to estimate the probability of $E_{1}\cap E_{2}$. We have

Without loss of generality, take $\|x_{0}\|=\|x_{1}\|=1$. Further, without loss of generality, take $x_{0}=e_{1}$ and $x_{1}=\cos\theta\ e_{1}+\sin\theta\ e_{2}$. The expected value is

where the second equality is because $2\cos\phi\cos(\theta-\phi)=\cos\theta+\cos(2\phi-\theta)$. ∎

Acknowledgements

PH acknowledges funding by the grant NSF DMS-1464525.

References