  We consider the problem of recovering a $K$-sparse complex signal $x$ from
$m$ intensity measurements. We propose the PhaseCode algorithm, and show that
in the noiseless case, PhaseCode can recover an arbitrarily-close-to-one
fraction of the $K$ non-zero signal components using only slightly more than
$4K$ measurements when the support of the signal is uniformly random, with
order-optimal time and memory complexity of $\Theta(K)$. It is known that the
fundamental limit for the number of measurements in compressive phase retrieval
problem is $4K - o(K)$ to recover the signal exactly and with no assumptions on
its support distribution. This shows that under mild relaxation of the
conditions, our algorithm is the first constructive \emph{capacity-approaching}
compressive phase retrieval algorithm: in fact, our algorithm is also
order-optimal in complexity and memory. 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 further demonstrate how PhaseCode can be robustified to
noise. 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.
