Papers › Fast Phase Retrieval from Local Correlation Measurements
Fast Phase Retrieval from Local Correlation Measurements
Mark Iwen, Aditya Viswanathan, Yang Wang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We develop a fast phase retrieval method which can utilize a large class of local phaseless correlation-based measurements in order to recover a given signal x ∈ℂᵈ (up to an unknown global phase) in near-linear 𝒪 ( d log⁴ d )-time. Accompanying theoretical analysis proves that the proposed algorithm is guaranteed to deterministically recover all signals x satisfying a natural flatness (i.e., non-sparsity) condition for a particular choice of deterministic correlation-based measurements. A randomized version of these same measurements is then shown to provide nonuniform probabilistic recovery guarantees for arbitrary signals x ∈ℂᵈ. Numerical experiments demonstrate the method's speed, accuracy, and robustness in practice -- all code is made publicly available. Finally, we conclude by developing an extension of the proposed method to the sparse phase retrieval problem; specifically, we demonstrate a sublinear-time compressive phase retrieval algorithm which is guaranteed to recover a given s-sparse vector x ∈ℂᵈ with high probability in just 𝒪(s log⁵ s ·logd)-time using only 𝒪(s log⁴ s ·logd) magnitude measurements. In doing so we demonstrate the existence of compressive phase retrieval algorithms with near-optimal linear-in-sparsity runtime complexities.
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.
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