The problem of sparse phase retrieval is considered where the goal is to recover a sparse complex valued vector (with s non zero elements) from the magnitudes of its linear measurements. Using a modified and partially randomized version of a newly proposed structured sampler, namely the Partial Nested Fourier Sampler (PNFS), it is shown to be possible to recover the unknown signal (up to a global phase ambiguity) from O(s log N) phaseless measurements where N is the dimension of the vector. The reconstruction is based on a novel idea of "decoupling" certain quadratic terms in the phaseless measurements acquired by the PNFS, leading to a simple l1-minimization-based recovery algorithm, without the need for "lifting" the unknown variable to a higher dimensional space. The proposed algorithm is also proved to be stable in presence of bounded noise.
['Heng Qiao', 'Piya Pal']
Sparse phase retrieval with near minimal measurements: A structured sampling based approach