Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space

Original · EN

We consider faithfully combining phase retrieval with classical compressed sensing. Inspired by the recent novel formulation for phase retrieval called PhaseMax, we present and analyze SparsePhaseMax, a linear program for phaseless compressed sensing in the natural parameter space. We establish that when provided with an initialization that correlates with an arbitrary k-sparse n-vector, SparsePhaseMax recovers this vector up to global sign with high probability from O(k n/k) magnitude measurements against i.i.d. Gaussian random vectors. Our proof of this fact exploits a curious newfound connection between phaseless and 1-bit compressed sensing. This is the first result to establish bootstrapped compressed sensing from phaseless Gaussian measurements under optimal sample complexity.