Fast and robust compressive phase retrieval with sparse-graph codes
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 ∈ ℂ<sup>n</sup>, from a set of m noisy quadratic measurements: y<sub>i</sub> = |a<sub>i</sub><sup>H</sup>s|<sup>2</sup> + w<sub>i</sub>; where a<sub>i</sub><sup>H</sup> ∈ ℂ<sup>n</sup> is the ith row of the measurement matrix A ∈ ℂ<sup>m×n</sup>, and w<sub>i</sub> is the additive noise to the ith measurement. We consider the regime where K = βn<sup>δ</sup>, δ ∈ (0; 1). We use the architecture of PhaseCode algorithm [1], 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<sup>1</sup> Θ(K log(n)) and computational complexity Θ(n log(n)), and the sublinear scheme recovers s with sample complexity Θ(K log<sup>3</sup>(n)) and computational complexity Θ(K log<sup>3</sup>(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.