PhaseCode: Fast and Efficient Compressive Phase Retrieval based on Sparse-Graph-Codes

We consider the problem of recovering a complex signal $x$ from $m$ intensity measurements. We address multiple settings corresponding to whether the measurement vectors are unconstrained choices or not, and to whether the signal to be recovered is sparse or not. However, 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 merge-and-color algorithms that are based on a sparse-graph-codes framework. As one instance, our 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. Next, motivated by some important practical classes of optical systems, we consider a Fourier-friendly constrained measurement setting, and show that its performance matches that of the unconstrained setting. In the Fourier-friendly setting that we consider, the measurement matrix is constrained to be a cascade of Fourier matrices and diagonal matrices. We also study the general non-sparse signal case, for which we propose a simple deterministic set of $3n-2$ measurements that can recover the n-length signal under some mild assumptions. Throughout, we provide extensive simulation results that validate the practical power of our proposed algorithms for the sparse unconstrained and Fourier-friendly measurement settings, for noiseless and noisy scenarios. 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.