Research map / Learning theory and algorithms / Matrix and tensor methods
A Fast and Provable Algorithm for Sparse Phase Retrieval
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a Newton-type hard-thresholding second-order algorithm for sparse phase retrieval that uses intensity loss for the objective and amplitude loss for support selection, achieving non-asymptotic quadratic local convergence with Omega(s^2 log n) Gaussian measurements.
Problem
Recovering an s-sparse signal (up to global sign) from magnitude-only (phaseless) Gaussian measurements with limited sample counts, where first-order sparse phase retrieval methods converge only linearly.
Approach
Combines a Newton step on the smooth intensity-based loss, restricted to a free-variable support identified by one IHT step on the amplitude-based loss, with fixed variables set to zero; this keeps per-iteration cost near first-order methods while giving quadratic local convergence.
Key results
- On noise-free sparse phase retrieval with n=5000, m=3000, s=80, the proposed method takes 0.0530 s versus 0.0813 s for HTP and 0.3630 s for ThWF.
- On a 30,000-dimensional wavelet-sparse signal with noise, the proposed method reaches PSNR 78 in 2.629 s, versus 71 for ThWF (11.586 s) and 62 for HTP (6.689 s).
- Theorem 1 gives quadratic local convergence after O(log(||x||/x_min)) iterations with m >= C s^2 log n Gaussian samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed second-order method instead of HTP | Sparse phase retrieval · Noise-free, sparsity 80 | running time (seconds): 0.0813 -> 0.0530 | Helped |
| Use the proposed second-order method instead of HTP | Sparse phase retrieval · Noise-free, sparsity 100 | running time (seconds): 0.2212 -> 0.1024 | Helped |
| Use the proposed second-order method instead of HTP | Sparse phase retrieval · Noisy (σ = 0.03), sparsity 80 | running time (seconds): 0.1134 -> 0.0803 | Helped |
| Use the proposed second-order method instead of HTP | Sparse phase retrieval · Noisy (σ = 0.03), sparsity 100 | running time (seconds): 0.2213 -> 0.1187 | Helped |
| Use the proposed method instead of HTP | Sparse phase retrieval reconstruction of a wavelet signal · Noisy wavelet signal, n = 30,000 | PSNR: 62 -> 78 | Helped |
| Use the proposed method instead of HTP | Sparse phase retrieval reconstruction of a wavelet signal · Noisy wavelet signal, n = 30,000 | running time (seconds): 6.689 -> 2.629 | Helped |
| Use amplitude-based loss to select Newton-update support instead of intensity-based loss (ablation) | Proposed sparse phase retrieval algorithm · Sparse phase retrieval convergence | convergence speed | Helped |
Surprising findings
- Using the amplitude-based loss to pick the free variables works better than using the intensity-based loss the algorithm optimizes.
Limitations
- Initialization still requires Omega(s^2 log n) samples, a sub-optimal dependence on s.
- Refinement stage needs the same sample complexity as initialization, unlike state-of-the-art refinement.
- Quadratic convergence is established only in a local neighborhood around the ground truth, after spectral initialization.
Experimental setup
Datasets: synthetic Gaussian sensing matrices wavelet-sparse synthetic signals
Benchmarks: synthetic sparse phase retrieval (n=5000, m=3000) phase transition experiments (n=3000) wavelet-sparse signal reconstruction (n=30000)
Metrics: relative error success rate running time PSNR
Baselines: ThWF SPARTA CoPRAM HTP
Builds on: ThWF SPARTA CoPRAM HTP Wirtinger flow
Closest papers by meaning
- Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors (NeurIPS 2021 · similarity 0.92)
- Fast Compressive Phase Retrieval under Bounded Noise (AAAI 2017 · similarity 0.91)
- Exponential Spectral Pursuit: An Effective Initialization Method for Sparse Phase Retrieval (ICML 2024 · similarity 0.91)
- Fast, Sample-Efficient Algorithms for Structured Phase Retrieval (NeurIPS 2017 · similarity 0.90)
- A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval (NeurIPS 2020 · similarity 0.89)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.