Source-linked AI summary
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Emmanuel J. Candes, Thomas Strohmer, Vladislav Voroninski
TL;DR
The paper addresses recovery of arbitrary signals from intensity measurements that omit phase information. It uses PhaseLift, a trace-norm minimization semidefinite program, and proves exact recovery with high probability from O(n log n) random measurements, together with robustness to additive noise. These results establish that a difficult phase-retrieval problem can, under the stated sensing conditions, be solved by convex programming.
Problem
Phase retrieval seeks to reconstruct signals from intensity-only measurements despite missing phase, while existing approaches can be computationally difficult or unstable.
Method
PhaseLift lifts quadratic measurements into a positive semidefinite matrix-recovery problem and relaxes rank minimization to trace-norm minimization.
Results
The trace-minimization program exactly recovers arbitrary real or complex signals up to global phase with high probability when m ≥ c0 n log n, and the method is robust to additive noise.
Takeaways & Limitations
The paper establishes a convex-programming route for exact and stable recovery in a class of otherwise combinatorial phase-retrieval problems.
Takeaways & Limitations
The analysis assumes independently uniform random sensing vectors and leaves structured random families and sharper stochastic-noise bounds for future work.
Abstract
from arXiv · showhide
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.
1 Introduction
Phase retrieval seeks to recover signals from intensity-only measurements despite missing phase, a problem that is computationally difficult and can be unstable under noise. The paper introduces PhaseLift, a convex semidefinite formulation that recovers arbitrary real or complex signals exactly with high probability using O(n log n) random measurements and remains stable under additive noise.
- Problem: Phase retrieval reconstructs signals from squared magnitudes |⟨x, z_i⟩|^2 when phase information cannot be measured.The setting includes Fourier intensity measurements and other sensing vectors.
- Problem: 14? The complex phase ambiguities make recovery combinatorial, and at least one version of phase retrieval is NP-hard.Efficient recovery therefore requires conditions on the number and choice of measurement vectors.
- Main result: The convex program is formally equivalent to the combinatorial phase-retrieval problem under appropriate random sensing conditions.The paper describes this as an exact convex solution to a computationally challenging nonconvex problem.
- Stability: The framework also provides stable recovery under additive noise, with small recovery error for bounded perturbations.The noise model uses quadratic intensity data with a noise vector satisfying ∥ν∥2 ≤ ϵ.
- Methodology: PhaseLift lifts quadratic vector recovery to rank-one matrix recovery over affine constraints and replaces NP-hard rank minimization with trace minimization over the positive semidefinite cone.The resulting trace-minimization problem is a semidefinite program; a rank-one solution is factorized to recover the signal up to a unit-modulus scalar.
- Main result: m ≥ c0 n log n measurements suffice for exact recovery of arbitrary real or complex signals with high probability.The trace-minimization program has a unique exact solution under the theorem’s random-sampling assumptions.
- Scope and discussion: The theory applies to one- or multi-dimensional signals and does not rely on algebraic-geometry tools.The paper identifies structured sensing families and sharper stochastic-noise bounds as directions for future work.
- Geometry: The affine measurement space can be tangent to the pointy positive semidefinite cone at xx∗, allowing a unique low-rank feasible point despite high ambient dimension.This geometric explanation underlies uniqueness of the recovered matrix.
2 Architecture of the Proof
The proof reduces recovery to injectivity and a dual-certificate condition for a semidefinite program, then establishes these properties using random measurement vectors and norm inequalities.
- Proof setup: The argument first treats the real case, then extends the proof to complex and more general settings.Rotational invariance permits reducing the real case to x = e1; Gaussian vectors are equivalent to uniform sphere samples after normalization.
- Recovery criterion: A sufficient condition for xx* to be the unique trace-minimization solution is injectivity of A on the tangent space plus a suitable dual certificate.The strategy strengthens injectivity so the certificate need not approximate the target as tightly.
- Recovery criterion: The key lemma uses two properties of A on positive semidefinite matrices together with a dual certificate to prove uniqueness of the minimizer.This lemma is the bridge from structural conditions on the measurement map to exact recovery by convex optimization.
- Measurement-map properties: The first measurement-map property resembles one-sided RIP-1, expressed in the 1-norm rather than the 2-norm.The paper motivates this choice by stating that a corresponding 2-norm RIP property is not expected to hold here.
- Perturbation analysis: The proof analyzes feasible perturbations H by separating tangent and orthogonal components and constraining their traces, ranks, and norms.The argument shows that the tangent component must vanish, then uses the measurement constraints and positivity to force H = 0.
3 Approximate ℓ1 Isometries
This section establishes approximate ℓ1-isometry properties for the measurement operator on low-rank matrices, using concentration bounds and covering arguments. These properties hold with high probability under sample sizes proportional to n, subject to the stated δ-dependent conditions.
- Section objective: The measurement operator is shown to satisfy stronger approximate-isometry properties than those strictly required for the main theorem.The proof targets conditions (2.2) and (2.3) for low-rank matrices.
- Rank-two matrices: For rank-2 matrices, m ≥ c0[δ^-2 log δ^-1]n yields the required property with probability at least 1 − 3e^−γ0mδ^2.The result applies to symmetric rank-2 matrices.
- Rank-two matrices: The rank-2 lower bound follows from f(t) ≥ 0.94 for every t ∈ [0,1], combined with concentration of empirical averages around their means.The random variables are controlled as sub-exponential variables and deviations are bounded using Chernoff-type inequalities.
- Uniformization: An ε-net of the unit sphere and [0,1] extends the fixed-matrix estimates uniformly over the full rank-2 class.The proof combines net bounds with approximation control and a union bound.
4 Dual Certificates
This section constructs and analyzes an inexact dual certificate for the trace-minimization program. Concentration bounds show that the certificate and approximate-isometry conditions hold jointly with high probability, yielding exact recovery.
- Certificate construction: The proof of exact recovery reduces to constructing an inexact dual certificate satisfying the conditions of Lemma 2.1.The certificate must lie in the range of A∗ and satisfy the required tangent-space and orthogonal-complement bounds.
- Certificate construction: The population certificate is perfect in the infinite-sample limit, with its tangent component equal to e1e∗1.The sample certificate is designed to approximate this population object.
- Certificate construction: A loose misfit bound of 1/2 eliminates the need for the golfing scheme and permits using a simple certificate candidate.The candidate can be viewed as the first iteration of Gross’s golfing scheme.
- Concentration analysis: Truncation makes the certificate summands bounded, enabling application of vector and matrix Bernstein inequalities.The truncation controls large coordinates such as |z1| while preserving the concentration argument.
- Final assembly: The certificate conditions require m > cn for one component and m > c′n log n for the other, while the union bound gives exact recovery with probability at least 1 − 3e^−γm/n.The constants are numerical and γ is positive.
5 The Complex Model
The real-valued argument extends to complex signals with modified constants and complex Gaussian measurements. The adjusted certificate and rank-2 estimates establish uniqueness of the trace-minimization solution in the complex model.
- Model extension: The complex proof follows the real proof’s main steps but requires changes for complex unit spheres and complex Gaussian variables.The real and imaginary parts of each measurement vector are independent with variance 1/2.
- Approximate isometry: The complex rank-2 estimate holds for Hermitian matrices when m ≥ c0[δ^-2 log δ^-1]n, with probability at least 1 − 3e^−γ0mδ^2.This is the complex analogue of the real rank-2 lemma.
- Numerical constants: The minimum of the complex-model function f(t) on [0,1] changes the numerical factors required by the recovery lemma.The complex proof therefore adjusts the constants in Lemma 2.2.
- Recovery result: The matrix e1e∗1 is the unique minimizer of the complex trace-minimization program.Rotational invariance extends the argument from e1 to arbitrary signals.
- Concentration analysis: The complex analysis uses |⟨z,u⟩|^2 distributed as 1/2χ^2(2), changing the moment calculations used in Bernstein bounds.The resulting moments are E|⟨z,u⟩|^2k = k!.
6 Stability
This section proves stability of the convex recovery method under additive measurement noise. The reconstruction error is controlled through the measurement residual, dual certificate, and low-rank decomposition, and the result transfers from Gaussian to spherical measurements.
- Stability framework: The stability proof parallels established stability arguments for matrix completion and related low-rank recovery methods.The section proves Theorem 1.2 using the same approximate-isometry and certificate framework.
- Measurement models: The stability theorem applies to uniformly sampled vectors on the sphere of radius √n and equivalently to independent standard Gaussian measurement vectors.The equivalence follows by normalizing Gaussian vectors to the sphere.
- Noisy measurements: For noisy data, the reconstruction error H satisfies ∥A(H)∥2 ≤ 2ϵ when the optimization residual and measurement noise are each bounded by ϵ.In the noiseless case, the corresponding measurement error is zero.
- Error control: The noisy proof bounds the tangent and orthogonal components of H proportionally to ϵ.The dual-certificate argument controls the trace of HT⊥ and the norm of HT.
- Signal estimation: The leading eigenvector of the recovered matrix provides an estimate of the signal, with perturbation theory connecting matrix error to signal-direction error.The analysis uses the top eigenvalue and the sin-θ theorem.
7 Numerical Simulations
Numerical experiments test PhaseLift under additive Gaussian and Poisson noise and varying measurement counts. The recovery degrades gracefully as SNR decreases, debiasing improves low-SNR results, and relative RMS decreases inversely with the number of measurements.
- Noise robustness: Ten-trial experiments evaluate PhaseLift on arbitrary complex signals with n = 128 and m = 6n random measurement vectors.The signal has independent Gaussian complex entries, and the measurement vectors are sampled independently on the unit sphere of C^n.
- Noise robustness: Gaussian and Poisson experiments use five SNR levels ranging from 5dB to 100dB without using noise statistics in reconstruction.The algorithm assumes only an upper bound on total noise power, as in Theorem 1.2.
- Noise robustness: Poisson-noise recovery degrades gracefully with decreasing SNR, while debiasing further improves reconstruction at low SNR.Gaussian-noise results are comparable; Figure 4 reports relative MSE and relative RMS for the original and debiased recovery.
- Noise robustness: Figure 5 evaluates Gaussian-noise recovery using relative MSE on a log scale and relative RMS for original and debiased estimates.The reported Gaussian-noise results are comparable to those obtained with Poisson noise.
- Oversampling: Doubling the number of measurements reduces the relative RMS error by a factor of two.The oversampling experiment varies m/n from 5 to 22, corresponding to m between n log n and 4.5n log n.
8 Discussion
The paper shows that arbitrary signals can be exactly recovered from random magnitude measurements by a tractable convex program, while also supporting recovery under additive noise. It identifies other measurement models, structured sensing families, and sharper stochastic-noise bounds as directions for future work.
- Discussion: Exact recovery up to global phase is achieved from magnitude measurements using a tractable convex program, with a noise-aware convex procedure robust to additive noise.The result applies to arbitrary signals and uses on the order of n log n magnitude measurements.
- Future work: Future work includes recovery from other intensity measurements, other sensing-vector families, structured random families, and sharper bounds under stochastic errors.The paper leaves these questions open rather than resolving them.