Fast compressive phase retrieval

Compressive Phase Retrieval refers to the problem of recovering an unknown sparse signal, upto a global phase constant, given only a small number of phaseless (or magnitude) measurements. This problem occurs in several areas of science - such as optics, astronomy and X-ray crystallography - where the underlying physics of the problem is such that we can only acquire phaseless (or intensity) measurements, and where the underlying signal is sparse (or sparse in an appropriate transform domain). We present here an essentially linear- in-sparsity-time compressive phase retrieval algorithm. We show that it is possible to stably recover k-sparse signals x ϵ Cⁿ from O (k log⁴ k · log n) measurements in only O (k log⁵ k · log n)-time. Numerical experiments show that the method is not only fast, but also stable to measurement noise.