Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns

Abstract

This note shows that we can recover a complex vector x in C^n exactly from on the order of n quadratic equations of the form |<a_i, x>|^2 = b_i, i = 1, ..., m, by using a semidefinite program known as PhaseLift. This improves upon earlier bounds in [3], which required the number of equations to be at least on the order of n log n. We also demonstrate optimal recovery results from noisy quadratic measurements; these results are much sharper than previously known results.

6 pages

References in corpus (1)

• On signal reconstruction without noisy phase

Cited by in corpus (11)

• Measure What Should be Measured: Progress and Challenges in Compressive Sensing
• Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
• 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
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Quantum Tomography From Few Full-Rank Observables
• Phase retrieval from very few measurements
• Reconstruction of Signals from Magnitudes of Redundant Representations: The Complex Case
• Conditions for Existence of Dual Certificates in Rank-One Semidefinite Problems
• Quantization and Greed are Good: One bit Phase Retrieval, Robustness and Greedy Refinements