Papers › Sample-Efficient Algorithms for Recovering Structured Signals from Magnitude-Only Measurements
Sample-Efficient Algorithms for Recovering Structured Signals from Magnitude-Only Measurements
Gauri Jagatap, Chinmay Hegde
We consider the problem of recovering a signal 𝐱^* ∈𝐑ⁿ, from magnitude-only measurements yᵢ = |⟨𝐚ᵢ,𝐱^*⟩| for i=[m]. Also called the phase retrieval, this is a fundamental challenge in bio-,astronomical imaging and speech processing. The problem above is ill-posed; additional assumptions on the signal and/or the measurements are necessary. In this paper we first study the case where the signal 𝐱^* is s-sparse. We develop a novel algorithm that we call Compressive Phase Retrieval with Alternating Minimization, or CoPRAM. Our algorithm is simple; it combines the classical alternating minimization approach for phase retrieval with the CoSaMP algorithm for sparse recovery. Despite its simplicity, we prove that CoPRAM achieves a sample complexity of O(s²logn) with Gaussian measurements 𝐚ᵢ, matching the best known existing results; moreover, it demonstrates linear convergence in theory and practice. Additionally, it requires no extra tuning parameters other than signal sparsity s and is robust to noise. When the sorted coefficients of the sparse signal exhibit a power law decay, we show that CoPRAM achieves a sample complexity of O(slogn), which is close to the information-theoretic limit. We also consider the case where the signal 𝐱^* arises from structured sparsity models. We specifically examine the case of block-sparse signals with uniform block size of b and block sparsity k=s/b. For this problem, we design a recovery algorithm Block CoPRAM that further reduces the sample complexity to O(kslogn). For sufficiently large block lengths of b=Θ(s), this bound equates to O(slogn). To our knowledge, this constitutes the first end-to-end algorithm for phase retrieval where the Gaussian sample complexity has a sub-quadratic dependence on the signal sparsity level.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections