Source-linked AI summary
Stable optimizationless recovery from phaseless linear measurements
Laurent Demanet, Paul Hand
TL;DR
Recovering a vector from phaseless measurements is difficult because magnitude constraints are nonconvex. The paper uses positive-semidefinite lifting to replace trace minimization with feasibility, proving unique and stable recovery with O(n log n) measurements under the stated random-sensing conditions.
Problem
Recovering a vector from phaseless linear measurements is difficult because the magnitude constraints are nonconvex.
Source: §1 · p. 1Method
The paper lifts recovery to a positive-semidefinite matrix feasibility problem, dispensing with trace minimization.
Source: §1 · p. 2Results
With O(n log n) measurements, the positive-semidefinite matrix solution is unique with high probability, and recovery is stable under perturbations.
Source: §1.1 · p. 3, §1.2 · p. 4Takeaways & Limitations
In this setting, semidefinite lifting suffices for stable recovery without trace minimization.
Source: §1 · p. 2, §1.2 · p. 4The paper does not claim trace minimization can be abandoned universally, since sensing-matrix structure appears to affect the number of measurements required.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We address the problem of recovering an n-vector from m linear measurements lacking sign or phase information. We show that lifting and semidefinite relaxation suffice by themselves for stable recovery in the setting of m = O(n log n) random sensing vectors, with high probability. The recovery method is optimizationless in the sense that trace minimization in the PhaseLift procedure is unnecessary. That is, PhaseLift reduces to a feasibility problem. The optimizationless perspective allows for a Douglas-Rachford numerical algorithm that is unavailable for PhaseLift. This method exhibits linear convergence with a favorable convergence rate and without any parameter tuning.
1 Introduction
The paper addresses the difficulty of recovering a vector from phaseless measurements and shows that positive-semidefinite lifting can yield unique, stable recovery with O(n log n) measurements. It removes PhaseLift’s trace-minimization step by casting recovery as a feasibility problem, while noting that sensing structure can affect measurement requirements.
1 Introduction
- Phaseless recovery is difficult because magnitude constraints are nonconvex, while alternating projections do not always converge to a solution.Lifting makes the measurements linear in the matrix xx*, enabling the positive-semidefinite relaxation used by PhaseLift.Source: §1 · pp. 1–2
- The paper shows trace minimization is unnecessary: recovery can find a positive-semidefinite matrix consistent with linear measurements by feasibility alone.The recovered vector is obtained from the matrix’s leading eigenvector.Source: §1 · p. 2, §1.1 · p. 3
- The paper does not advocate abandoning trace minimization in every phase-retrieval setting, since sensing-matrix structure appears to affect the measurements required.The introduction also reports numerical observations suggesting Gaussian sensing may require O(n^2) measurements for optimizationless recovery; these simulations are not shown.Source: §1 · p. 2
1.1 Problem Statement and Main Result
- With O(n log n) measurements, the positive-semidefinite matrix consistent with the measurements is unique with high probability, yielding vector recovery up to global phase.In the real-valued case, the ambiguity is only a minus sign.Source: §1.1 · p. 3
1.2 Stability result
- With O(n log n) measurements, every feasible positive-semidefinite matrix lies within an O(ε) ball of X0 with high probability, establishing stability under measurement perturbations.The paper states this result for sufficiently large measurement-count constant c.Source: §1.2 · p. 4
2 Proof of Main Result
The proof replaces an exact dual certificate with an inexact one, using ℓ1-isometry properties to restrict feasible matrices to a cone. With O(n log n) random measurements, the certificate conditions hold with high probability and imply unique recovery.
2.1 About Dual Certificates
- Exact certificates require a zero T component, whereas the inexact construction permits a tractable approximation in the range of A*.The paper uses an RIP-like injectivity condition to justify relaxing the exact nullspace requirement.Source: §2.1 · p. 5, §2 · p. 5
- An inexact certificate separates X0 from the rest of a cone containing feasible matrices, so its T component need not be exactly zero.The cone restriction follows from ℓ1-isometry properties.Source: §2.1 · p. 5, §2.2 · p. 6, Figure 1 · p. 6
2.2 Central Lemma on Inexact Dual Certificates
- The central lemma combines ℓ1-isometry conditions with an inexact dual certificate to establish that X0 is the unique feasible positive semidefinite matrix.The proof places feasible solutions in a cone, then uses the certificate conditions to force their difference from X0 to vanish.Source: §2.2 · pp. 6–7
2.3 Proof of Theorem 1 and Corollary 2
- With m > cn log n, the ℓ1-isometry and inexact-certificate conditions hold with high probability, yielding uniqueness of the lifted solution.The stated probability bound is at least 1 − e^(−γm/n) for suitable constants.Source: §2.3 · p. 7
3 Existence of Inexact Dual Certificate
The section constructs and bounds an inexact dual certificate for the recovery proof. Its required certificate properties hold when the number of measurements is sufficiently large, including an O(n log n) condition.
3.1 Motivation for the Dual Certificate
- The certificate construction truncates random-matrix terms so that concentration inequalities for bounded vectors can be applied.The passage describes truncating Yi through the event Ei before completing the certificate derivation.Source: §3.1 · p. 8, §3 · p. 8
3.2 Bounds on ¯Y
- For m ≥ cn log n, the certificate bounds establish the required approximation to 2(I − e1e1*) and support the inexact-certificate conditions.The stated lemmas give bounds on the certificate and its components for sufficiently large n.Source: §3.2 · p. 8
3.3 Proof of Lemma 2: ¯Y on T
- The bound on the certificate's T component follows from a vector Bernstein argument under a sufficiently large measurement count.The proof states that Lemma 2 follows by choosing parameters and m ≥ cn.Source: §3.3 · pp. 9–10
3.4 Proof of Lemma 3: ¯Y on T ⊥
- The T⊥ component is bounded with exponentially high probability using a scalar Bernstein argument and parameter choices controlling the truncation error.The proof gives a probability of at least 1 − 2e^(−γm) for some γ > 0.Source: §3.4 · p. 11
4 Stability
The stability argument extends certificate-based uniqueness to noisy measurements. It establishes stability for the lifted matrix problem and then transfers that result to vector recovery.
4 Stability
- Under the stated isometry and certificate conditions, the lifted recovery problem is stable to measurement error.The lemma assumes a certificate Y = A*λ with ∥λ∥1 ≤ 5.Source: §4 · p. 13
4.1 Dual Certificate Property
- The constructed certificate satisfies the required dual-certificate bound ∥λ∥1 ≤ 5.The passage derives this bound from the certificate construction and the ℓ1-isometry property.Source: §4.1 · p. 14
4.2 Proof of Corollary 4
- Stability of the lifted matrix solution implies stability of the unlifted vector recovery problem.The proof uses the relation X0 = x0x0* and a spectral perturbation bound.Source: §4.2 · pp. 14–15
5 Complex Case
The complex-valued case follows the real-valued proof with modified sensing assumptions and a slightly different certificate construction. The stated certificate conditions yield uniqueness with high probability.
5 Complex Case
- For complex sensing vectors with independent standard-normal real and imaginary parts, the ℓ1-isometry conditions have weaker constants than in the real case.The proof otherwise has only a few minor differences from the real-valued case.Source: §5 · p. 15
- The complex-case certificate conditions imply that X0 is the unique solution, and the paper states that these conditions hold with high probability.The certificate construction differs because S(X) = X + Tr(X)I and S−1(X) = X − 1…Source: §5 · p. 15
- The remaining modifications to the proof follow those in.Source: §5 · p. 15
6 Numerical Simulations
The simulations show that optimizationless recovery can be implemented with Douglas–Rachford and Nesterov methods, and examine their measurement requirements and convergence. The feasibility formulation uses projections onto the measurement-consistent affine space and the positive semidefinite cone, avoiding trace minimization.
6.1 Optimization Framework
- Setting λ = 0 reduces the soft data-fit formulation to feasibility, while formulation (42) requires no parameters.Douglas–Rachford was considered as a backward-backward method because it often performs better than POCS.Source: §6.1 · p. 16
- The optimizationless formulation seeks a positive semidefinite matrix consistent with linear measurements, reducing recovery to feasibility rather than trace minimization.Its data-fit and positive-semidefinite constraints are represented by projections onto an affine space and the PSD cone.Source: §6.1 · p. 16
6.2 Numerical Results
- Recovery required approximately linear growth in n measurements, and artifacts appeared near m = n(n+1)/2, where the noisy measurement equations need not have a positive semidefinite solution.The experiments used noisy data with ε = 1/10 and averaged 10 samples per (n, m) pair.Source: §6.2 · p. 17, Figure 2 · p. 18
- For noiseless data, feasibility iterations converged linearly under both methods; with noisy data, convergence tapered around the noise level.Douglas–Rachford had a favorable convergence rate without parameter tuning; nonzero λ in Nesterov PhaseLift led to a minimizer different from X0.Source: §6.2 · pp. 17–18