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.

References in corpus (5)

• Compressive Direct Measurement of the Quantum Wave Function
• Sparse Signal Recovery from Quadratic Measurements via Convex Programming
• Sparse Phase Retrieval: Convex Algorithms and Limitations
• Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes
• Hanson-Wright inequality and sub-gaussian concentration

Cited by in corpus (1)

• Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes