Sparse phase retrieval with near minimal measurements: A structured sampling based approach

Abstract

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 l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -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.