Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes

Abstract

In this paper, we tackle the compressive phase retrieval problem in the presence of noise. The noisy compressive phase retrieval problem is to recover a $K$-sparse complex signal $s\in {\mathbb{C}}^n$, from a set of $m$ noisy quadratic measurements: $y_i=|a_i^{H}s{|}^2+w_i$, where $a_i^H\in {\mathbb{C}}^n$ is the $i$th row of the measurement matrix $A\in {\mathbb{C}}^{m\times n}$, and $w_i$ is the additive noise to the $i$th measurement. We consider the regime where $K=\beta n^{\delta }$, with constants $\beta >0$ and $\delta \in (0,1)$. We use the architecture of PhaseCode algorithm, and robustify it using two schemes: the almost-linear scheme and the sublinear scheme. We prove that with high probability, the almost-linear scheme recovers $s$ with sample complexity $\Theta (K\log (n))$ and computational complexity $\Theta (n\log (n))$, and the sublinear scheme recovers $s$ with sample complexity $\Theta (K{\log }^3(n))$ and computational complexity $\Theta (K{\log }^3(n))$. To the best of our knowledge, this is the first scheme that achieves sublinear computational complexity for compressive phase retrieval problem. Finally, we provide simulation results that support our theoretical contributions.