Fast Phase Retrieval from Local Correlation Measurements
arXiv:1501.02377
Abstract
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 (up to an unknown global phase) in near-linear -time. Accompanying theoretical analysis proves that the proposed algorithm is guaranteed to deterministically recover all signals 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 . 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 -sparse vector with high probability in just -time using only magnitude measurements. In doing so we demonstrate the existence of compressive phase retrieval algorithms with near-optimal linear-in-sparsity runtime complexities.
arXiv commentadded more empirical evaluations/performance comparisons, clarifications/additions to introduction/abstract
References in corpus (7)
- Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
- A unified evaluation of iterative projection algorithms for phase retrieval
- Compressive Phase Retrieval via Generalized Approximate Message Passing
- Sparse Phase Retrieval from Short-Time Fourier Measurements
- Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
- Phase Retrieval with Random Phase Illumination
- Stable phase retrieval with low-redundancy frames