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

arXiv: https://arxiv.org/abs/1611.05985 · HTML: https://mlsanity.com/paper/1611.05985/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2016.

## Built on by (most cited first, 2 of 2)

- [Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent](https://mlsanity.com/paper/2105.03678/) (2021)
- [Low Complexity Regularized Phase Retrieval](https://mlsanity.com/paper/2407.16413/) (2024)

## Abstract (arXiv)

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 fracnk) 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.