PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
arXiv:1109.4499
Abstract
Suppose we wish to recover a signal x in C^n from m intensity measurements of the form |<x,z_i>|^2, i = 1, 2,..., m; that is, from data in which phase information is missing. We prove that if the vectors z_i are sampled independently and uniformly at random on the unit sphere, then the signal x can be recovered exactly (up to a global phase factor) by solving a convenient semidefinite program---a trace-norm minimization problem; this holds with large probability provided that m is on the order of n log n, and without any assumption about the signal whatsoever. This novel result demonstrates that in some instances, the combinatorial phase retrieval problem can be solved by convex programming techniques. Finally, we also prove that our methodology is robust vis a vis additive noise.
References in corpus (2)
Cited by in corpus (15)
- Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
- Phase Recovery, MaxCut and Complex Semidefinite Programming
- Saving phase: Injectivity and stability for phase retrieval
- Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
- Stable phase retrieval with low-redundancy frames
- Invertibility and Robustness of Phaseless Reconstruction
- On Conditions for Uniqueness in Sparse Phase Retrieval
- Blind Identification of ARX Models with Piecewise Constant Inputs
- On Gradient Descent Algorithm for Generalized Phase Retrieval Problem
- Sparse Signal Processing with Frame Theory
- Quantization and Greed are Good: One bit Phase Retrieval, Robustness and Greedy Refinements
- Recovery of Sparse 1-D Signals from the Magnitudes of their Fourier Transform
- An elementary approach for the phase retrieval problem
- An Algorithm for Exact Super-resolution and Phase Retrieval
- Phase retrieval for the Cauchy wavelet transform