# Sparse Phase Retrieval: Convex Algorithms and Limitations

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2013.

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

- [Generalization Guarantees for Neural Architecture Search with Train-Validation Split](https://mlsanity.com/paper/2104.14132/) (2021)
- [Image Reconstruction without Explicit Priors](https://mlsanity.com/paper/2303.12217/) (2023)
- [Discovering Structure From Corruption for Unsupervised Image Reconstruction](https://mlsanity.com/paper/2304.05589/) (2023)
- [Alternating Phase Langevin Sampling with Implicit Denoiser Priors for Phase Retrieval](https://mlsanity.com/paper/2211.00884/) (2022)
- [One-Bit Quadratic Compressed Sensing: From Sample Abundance to Linear Feasibility](https://mlsanity.com/paper/2303.09594/) (2023)
- [Convex Augmentation for Total Variation Based Phase Retrieval](https://mlsanity.com/paper/2205.00834/) (2022)
- [Low Complexity Regularized Phase Retrieval](https://mlsanity.com/paper/2407.16413/) (2024)
- [prNet: Data-Driven Phase Retrieval via Stochastic Refinement](https://mlsanity.com/paper/2507.09608/) (2025)

## Abstract (arXiv)

We consider the problem of recovering signals from their power spectral density. This is a classical problem referred to in literature as the phase retrieval problem, and is of paramount importance in many fields of applied sciences. In general, additional prior information about the signal is required to guarantee unique recovery as the mapping from signals to power spectral density is not one-to-one. In this paper, we assume that the underlying signals are sparse. Recently, semidefinite programming (SDP) based approaches were explored by various researchers. Simulations of these algorithms strongly suggest that signals upto o(√n) sparsity can be recovered by this technique. In this work, we develop a tractable algorithm based on reweighted l1-minimization that recovers a sparse signal from its power spectral density for significantly higher sparsities, which is unprecedented. We discuss the square-root bottleneck of the existing convex algorithms and show that a k-sparse signal can be efficiently recovered using O(k2logn) phaseless Fourier measurements. We also show that a k-sparse signal can be recovered using only O(k log n) phaseless measurements if we are allowed to design the measurement matrices.