Source-linked AI summary
Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns
Emmanuel J. Candes, Xiaodong Li
TL;DR
The paper asks whether complex signals can be recovered from roughly n quadratic measurements, improving on earlier n log n requirements. It uses PhaseLift and proves exact universal recovery with exponentially small failure probability, while also obtaining sharp guarantees for noisy measurements.
Problem
The paper addresses whether PhaseLift can recover signals from a number of quadratic equations on the order of the number of unknowns, rather than requiring n log n equations.
Method
The paper uses PhaseLift, a semidefinite-programming relaxation that replaces the nonconvex rank constraint for lifted quadratic measurements.
Results
PhaseLift exactly recovers all input signals with probability at least 1 − O(e^−γm) when the number of equations is a sufficiently large constant times n.
Takeaways & Limitations
Quadratic phase-retrieval systems can be solved by semidefinite programming with about as many equations as unknowns, and the paper also gives sharper optimal noisy-recovery results.
Takeaways & Limitations
The guarantees are stated for the complex and real measurement models introduced in the paper, with independently and identically distributed measurement vectors.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies whether PhaseLift can recover signals from quadratic measurements using only on the order of n equations, and answers this affirmatively with universal, exponentially reliable recovery. It also extends the result to noisy measurements with sharp recovery guarantees.
- Problem: Quadratic measurements provide magnitudes |⟨a_i, x⟩|^2 while the unknown signal x0 and measurement vectors a_i are complex-valued.The phase-retrieval formulation uses b_i = |⟨a_i, x0⟩|^2 and lifts xx∗ to a matrix variable X.
- Method: PhaseLift replaces the nonconvex rank constraint with a convex surrogate and recovers the signal through semidefinite programming.In the noisy setting, it finds a positive semidefinite matrix fitting the observations in ℓ1, then extracts a best-rank-one approximation.
- Noiseless recovery: m ≥ c0 n equations suffice for exact PhaseLift recovery with probability at least 1 − O(e^−γm), for a sufficiently large constant c0.The guarantee applies to the complex and real models described in the paper.
- Noiseless recovery: Exact recovery holds simultaneously over all input signals, rather than only for a fixed signal.The associated null-space property is tangent to the PSD cone at all rank-one elements.
- Improvement: The result removes the earlier n log n equation requirement and makes the failure probability exponentially small in the number of measurements.The paper states that the earlier proof could not remove the logarithmic factor and required a different argument.
- Noisy recovery: For noisy measurements, ℓ1 data fitting followed by leading-eigenvector extraction yields accurate signal estimates, with bounds described as optimal.For Gaussian models, the noisy guarantee has the same probability as the noiseless case; for the uniform model, failure is exponentially small in n.
2 Proofs
The proofs establish exact and stable PhaseLift recovery by constructing dual certificates, first for fixed signals and then uniformly over all signals using concentration and continuity arguments.
- 2 Proofs: The proof transfers between Gaussian and uniform measurement models, with full equivalence in the noiseless case and nearly unchanged success probability in the noisy case.This reduction allows the main analysis to focus on the real-valued Gaussian setting.
- 2.1 Dual certificates: The intermediate dual-certificate lemma is novel and underpins the proof of uniform exact recovery.The construction is first established for a fixed x0 and then extended to all x0.
- 2.1 Dual certificates: A dual certificate Y in the range of A∗, with controlled tangent and orthogonal components, makes x0x0∗ PhaseLift’s unique feasible point.The proof uses positivity of the orthogonal component and orthogonality to the measurement null space to force any feasible perturbation to vanish.
- 2.1 Dual certificates: For fixed x0, a certificate is constructed with probability at least 1 −O(e−γm) using a truncated Gaussian construction and concentration bounds.The argument controls Wishart and sub-Gaussian random-matrix terms when m ≥ cn for sufficiently large c.
- 2.2 Uniform recovery: An ε-net over the unit sphere plus a continuity argument extends fixed-signal certificates to every signal, while retaining exponentially small failure probability.The net has cardinality at most (1 + 2/ε)^n, and the certificate coefficients can satisfy ∥λ∥∞ ≤ 7/m.
- 2.3 Stability: The noisy-recovery proof reuses the dual-certificate argument, and the resulting Frobenius-norm error bound is optimal under ℓ1-bounded measurement noise.The optimality argument uses indistinguishable scaled signals whose errors can reach δ∥x0x0∗∥F = δ.