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 (6)

• Optimal detection of sparse principal components in high dimension
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• Sparse Phase Retrieval via Truncated Amplitude Flow
• Near-optimal phase retrieval of sparse vectors
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow

Cited by in corpus (12)

• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Sparse Phase Retrieval via Truncated Amplitude Flow
• Global Guarantees for Blind Demodulation with Generative Priors
• Hadamard Wirtinger Flow for Sparse Phase Retrieval
• Solving Equations of Random Convex Functions via Anchored Regression
• Learning Illumination Patterns for Coded Diffraction Phase Retrieval
• Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
• A stochastic alternating minimizing method for sparse phase retrieval
• Two-step PR-scheme for recovering signals in detectable union of cones by magnitude measurements