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

Abstract

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\log \frac{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.

References in corpus (1)

• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax

Cited by in corpus (3)

• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Global Guarantees for Blind Demodulation with Generative Priors
• A stochastic alternating minimizing method for sparse phase retrieval