# A Fast and Provable Algorithm for Sparse Phase Retrieval

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2023.

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

- [Manifold constrained steepest descent for smooth and closed-set optimization](https://mlsanity.com/paper/2601.21487/) (2026)
- [Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2502.21099/) (2025)
- [Tunable Domain Adaptation Using Unfolding](https://mlsanity.com/paper/2603.26931/) (2026)

## Abstract (arXiv)

We study the sparse phase retrieval problem, which seeks to recover a sparse signal from a limited set of magnitude-only measurements. In contrast to prevalent sparse phase retrieval algorithms that primarily use first-order methods, we propose an innovative second-order algorithm that employs a Newton-type method with hard thresholding. This algorithm overcomes the linear convergence limitations of first-order methods while preserving their hallmark per-iteration computational efficiency. We provide theoretical guarantees that our algorithm converges to the s-sparse ground truth signal xnatural ∈ ℝn (up to a global sign) at a quadratic convergence rate after at most O(log (Vertxnatural Vert /xminnatural)) iterations, using Omega(s2log n) Gaussian random samples. Numerical experiments show that our algorithm achieves a significantly faster convergence rate than state-of-the-art methods.