PhaseCode: Fast and efficient compressive phase retrieval based on sparse-graph codes

We consider the problem of recovering a complex signal x ϵ Cⁿ from m intensity measurements of the form |a_ix|, 1 ≤ i ≤ m, where a_i is a measurement row vector. Our main focus is on the case where the measurement vectors are unconstrained, and where x is exactly K-sparse, or the so-called general compressive phase-retrieval problem. We introduce PhaseCode, a novel family of fast and efficient algorithms (that includes Unicolor PhaseCode and Multicolor PhaseCode) that are based on a sparse-graph coding framework. As one instance, our Unicolor PhaseCode algorithm can provably recover, with high probability, all but a tiny 10^-7 fraction of the significant signal components, using at most m = 14K measurements, which is a small constant factor from the fundamental limit, with an optimal O(K) decoding time and an optimal O(K) memory complexity. We provide extensive simulation results that validate the practical power of our proposed algorithms. A key contribution of our work is the novel use of coding-theoretic tools like density evolution methods for the design and analysis of fast and efficient algorithms for compressive phase-retrieval problems. This contrasts and complements popular approaches to the phase retrieval problem based on alternating-minimization, convex-relaxation, and semi-definite programming.