PaperlayerView exact revision on arXiv

Source-linked AI summary

Phase Recovery, MaxCut and Complex Semidefinite Programming

Irène Waldspurger, Alexandre d'Aspremont, Stéphane Mallat

arXiv:1206.0102v3math.OC

TL;DR

Phase retrieval seeks to recover a complex signal from magnitude-only measurements, despite nonconvexity and possible instability. The paper separates amplitudes and phases, formulates a MaxCut-like semidefinite relaxation called PhaseCut, and solves it with block coordinate descent. The approach has low per-iteration cost and is evaluated across three phase-recovery settings, while its approximation guarantees and iteration bounds remain limited.

  • Problem

    Phase retrieval seeks to reconstruct a complex signal from magnitude-only linear measurements, and greedy methods can stall at local minima.

  • Method

    The paper formulates phase recovery over unit-modulus complex phases, introduces the PhaseCut MaxCut-like SDP relaxation, and solves it using block coordinate descent.

  • Results

    Each block coordinate descent iteration requires only a matrix-vector product, and the method is evaluated on three different phase-recovery problems.

  • Takeaways & Limitations

    PhaseCut provides a computationally simple relaxation whose information can also support approximate and robust phase-recovery solutions.

  • Takeaways & Limitations

    PhaseCut does not inherit classical MaxCut constant approximation ratios, and no fully explicit iteration bound is known for its block coordinate descent algorithm.

Abstract

from arXiv · show

Phase retrieval seeks to recover a signal x from the amplitude |Ax| of linear measurements. We cast the phase retrieval problem as a non-convex quadratic program over a complex phase vector and formulate a tractable relaxation (called PhaseCut) similar to the classical MaxCut semidefinite program. We solve this problem using a provably convergent block coordinate descent algorithm whose structure is similar to that of the original greedy algorithm in Gerchberg-Saxton, where each iteration is a matrix vector product. Numerical results show the performance of this approach over three different phase retrieval problems, in comparison with greedy phase retrieval algorithms and matrix completion formulations.

1. INTRODUCTION

Phase recovery reconstructs complex signal phases from magnitude-only linear measurements, a problem arising in imaging and audio applications. The paper formulates a PhaseCut relaxation related to MaxCut and develops an efficient convergent solver.

  • Applications: Phase recovery is relevant to X-ray, diffraction, microscopy, and audio signal processing because detectors often record amplitudes without phases.These applications motivate recovering complex phase information from magnitude measurements.
  • Motivation: Magnitude-only measurements can leave phase recovery nonunique or unstable, depending on the measurement operator A.Random Gaussian measurements can provide uniqueness and stability, while some Fourier settings remain nonunique or unstable.
  • Prior approaches: Existing greedy algorithms alternate projections but can stall at local minima.PhaseLift instead convexifies the problem by lifting xx* to a rank-one Hermitian matrix.
  • Contributions: The paper formulates phase recovery as a quadratic optimization over the unit complex torus and relaxes it using the MaxCut-like PhaseCut SDP.PhaseCut is typically larger than PhaseLift but has singleton constraint matrices.
  • Contributions: PhaseCut admits a provably convergent block coordinate descent method with iterations comparable in structure to Gerchberg–Saxton matrix-vector updates.The paper also relates modified PhaseCut and PhaseLift formulations under injectivity and nonzero-measurement assumptions.

2. PHASE RECOVERY

The paper separates measured amplitudes from unknown unit-modulus phases, reducing phase recovery to a nonconvex quadratic program. It then lifts that formulation into a complex MaxCut-like semidefinite relaxation called PhaseCut.

  • Problem formulation: The recovery problem seeks x from amplitudes b = |Ax| of n linear measurements.Here A is an n×p complex matrix and b is real-valued.
  • Greedy methods: Gerchberg–Saxton alternates projection onto the image of A with amplitude adjustment, but typically converges to an infeasible stationary point.The nonconvexity of the amplitude set prevents a general guarantee of reaching the intersection with the image of A.
  • Phase formulation: Writing Ax = diag(b)u with |u_i| = 1 separates amplitude and phase variables and yields a quadratic optimization over u.Eliminating x by least squares produces the reduced phase-only problem.
  • Phase formulation: The quadratic objective minimizes the component of diag(b)u orthogonal to the image of A.The matrix I − AA† is the orthogonal projector onto the complement of that image.
  • Greedy methods: The phase-only greedy algorithm converges to a stationary point that is generally not globally optimal and often shares stationary points with Gerchberg–Saxton.Updating all phase coordinates directly can require O(n^2) operations per iteration.
  • PhaseCut relaxation: Dropping the rank-one constraint from U = uu* produces the convex PhaseCut SDP: minimize Tr(UM) subject to diag(U) = 1 and U ⪰ 0.A rank-one optimum gives an exact phase solution; otherwise, a normalized leading eigenvector provides an approximation.

3. ALGORITHMS

The algorithms section develops scalable methods for solving PhaseCut, emphasizing its SDP structure, barrier formulation, and block coordinate descent. It also describes randomization, structural reductions, and the limits of MaxCut approximation guarantees.

  • SDP algorithms: The PhaseCut dual is a minimum-eigenvalue maximization problem, and exact recovery corresponds to primal value zero and λ_min(M) = 0.Both primal and dual formulations can be solved efficiently.
  • SDP algorithms: Generic interior-point methods become prohibitive as n grows because each iteration can require O(n^3) matrix inversion.Specialized methods exploit singleton diagonal constraints, while first-order methods trade per-iteration cost against precision dependence.
  • Block coordinate descent: A log-determinant barrier controls distance from the PhaseCut optimum, enabling block updates based on a block-determinant identity.Each block subproblem reduces to a quadratic-form minimization.
  • Block coordinate descent: Block coordinate descent has linear convergence in this setting, although no fully explicit iteration bound is known.Each iteration requires only a matrix-vector product, yielding low per-iteration cost.
  • Randomization: Gaussian randomization extracts feasible unit-modulus candidates from a PhaseCut solution by normalizing sampled coordinates and selecting the lowest objective.The SDP solution can also support robust formulations under a Gaussian phase model.
  • Limitations: PhaseCut does not inherit the constant approximation ratios established for classical MaxCut because it minimizes rather than maximizes.The distinction applies despite the shared MaxCut-type SDP structure.
  • Structural information: Known symmetries or aligned phases can reduce the problem dimension and produce computational savings.Aligned phases can be fixed to one through additional SDP constraints.

4. MATRIX COMPLETION & EXACT RECOVERY CONDITIONS

The paper compares PhaseCut with PhaseLift and a weaker trace-free relaxation. It explains their geometric relationship and reports that, under Gaussian measurements, the weaker relaxation can be tight under the same conditions as PhaseLift.

  • PhaseLift: PhaseLift casts phase recovery as a positive-semidefinite matrix completion problem in X, with exact recovery corresponding to X = xx*.The trace-minimization relaxation is tight when the optimum is unique, rank one, and has leading eigenvector x.
  • Weak PhaseLift: The paper introduces Weak PhaseLift as a formulation more directly related to PhaseCut and easier to interpret geometrically.When the identity lies in the span of the measurement outer products, trace minimization becomes redundant.
  • Weak PhaseLift: PhaseLift solutions also solve Weak PhaseLift, but the converse need not hold.Interior-point methods may select an analytic-center solution of Weak PhaseLift that differs substantially from the minimum-trace solution.
  • Comparison: Removing trace minimization does not appear to alter practical performance in the reported experiments.For Gaussian random measurements, prior work shows Weak PhaseLift is tight with high probability under the same conditions as PhaseLift.
  • Relationship to PhaseCut: PhaseCut can be interpreted as a projection-based phase recovery formulation, supporting later stability analysis.The relaxation is expressed through the phase vector and measurement magnitudes rather than directly through the lifted signal matrix.

4.2. Phase Recovery as a Projection.

PhaseCut reformulates phase recovery as a projection problem over intersections involving the positive semidefinite cone, fixed-diagonal matrices, and the measurement-consistency set. This structure supports comparisons with Weak PhaseLift and projection-based algorithms.

  • Projection formulation: PhaseCut minimizes Tr(V(I−AA†)) subject to diag(V)=b2 and V⪰0.The formulation is an SDP in the Hermitian matrix variable V.
  • Projection formulation: The objective equals a distance to the measurement-consistency set, with the trace norm providing the corresponding projection interpretation.The paper identifies d1 as the distance associated with the trace norm.
  • Projection formulation: PhaseCut can be interpreted as projecting toward the fixed-diagonal set Hb while remaining in the positive semidefinite cone and measurement-consistency set F.The sets are represented through the constraints defining Hb and F.
  • Comparison with Weak PhaseLift: Weak PhaseLift and PhaseCut are comparable projection procedures, but they move between the relevant cone intersections in opposite directions.Weak PhaseLift moves a point toward F, whereas PhaseCut moves a point toward Hb.
  • Comparison with Weak PhaseLift: The paper extends the parallel between the relaxations by comparing their tightness in noiseless settings and their stability under noisy measurements.These comparisons motivate the subsequent equivalence and stability results.

4.3. Tightness of the Semidefinite Relaxation.

The paper establishes a correspondence between PhaseCutMod and PhaseLift under injectivity, nonzero measurements, and solvability assumptions. In the noiseless case, this correspondence yields equivalent tightness, while noisy performance can differ.

  • Algorithmic implementation: PhaseCutMod can be obtained from PhaseCut by adding a sufficiently small γB penalty, allowing existing greedy or SDP algorithms to be reused with negligible complexity impact.The construction uses SDP(M+γB) for γ>0 sufficiently small.
  • Equivalence of relaxations: Under nonzero measurements, injective A, and solvability, the map Φ is a bijection between feasible points of PhaseCutMod and PhaseLift.The result identifies the feasible sets of the two relaxations through Φ.
  • Equivalence of relaxations: PhaseCutMod is tight whenever PhaseLift is, provided A is injective, every bi is nonzero, and the reconstruction problem has an exact solution.Tightness means that PhaseCutMod has a unique rank-one solution.
  • Equivalence of relaxations: In the noiseless case, PhaseCutMod and PhaseLift are equivalent relaxations under the stated assumptions.The paper also notes an analogous equivalence between Weak PhaseLift and PhaseCut.
  • Noisy measurements: When measurements are noisy, the performances of PhaseCut and PhaseLift-related relaxations may no longer match, even though their noiseless formulations are equivalent.The paper studies stability relations separately in the noisy setting.

4.4. Stability in the Presence of Noise.

The paper defines stability through reconstruction error under small measurement perturbations and shows that PhaseCut inherits a comparable stability order from Weak PhaseLift. A converse implication is not established for sparse measurements.

  • Stability definition: A method is C-stable at x0 when every minimizer under sufficiently small bnoise remains within the prescribed error bound.The definition applies separately to PhaseCut and Weak PhaseLift.
  • Stability definition: A C-stable algorithm produces O(C∥bnoise∥2) reconstruction error under measurement noise.This perturbation result motivates the stability definition.
  • Stability transfer: If Weak PhaseLift is C-stable at x0, then PhaseCut is (2C+2)-stable at x0.The theorem provides a stability constant of the same order, with the displayed expression subject to the paper’s stated notation.
  • Stability transfer: The proof constructs an approximate Weak PhaseLift solution from a PhaseCut solution, enabling the stability implication from Weak PhaseLift to PhaseCut.The argument does not establish the converse construction in general.
  • Stability limitations: When some coefficients of b are very small, rescaling a Weak PhaseLift solution can produce a large discrepancy, and this occurs in practice.Small coefficients can make the rescaling factors Ri large even when the diagonal constraint error is small.
  • Stability limitations: For random Gaussian measurements under the stated assumptions, Weak PhaseLift and therefore PhaseCut are C-stable with high probability for some parameter-independent C.The conclusion relies on assumptions about noisy Weak PhaseLift behavior and the cited Gaussian measurement bounds.

4.5. Perturbation Results.

The paper compares the relative complexity of solving PhaseLift and PhaseCut semidefinite programs across algorithmic choices and precision targets. The numerical experiments use a penalized PhaseLift formulation.

  • Perturbation results: PhaseLift and PhaseCut are both semidefinite programs whose solution complexity depends on the algorithmic choice and target precision.The paper frames the comparison in terms of relative computational complexity.
  • Perturbation results: The numerical experiments solve a penalized formulation of PhaseLift rather than directly the unpenalized problem.This implementation choice is noted when discussing solver complexity.

4.6. Complexity Comparisons.

PhaseCut’s structural simplicity can reduce computational cost relative to PhaseLift, especially for high-precision solutions, while block coordinate descent offers lower iteration complexity but lacks fully explicit iteration bounds.

  • 4.6. Complexity Comparisons.: Weighted trace-norm iterations can reduce rank in related semidefinite programs, but trace minimization is unnecessary in PhaseCut because its trace is fixed.The paper notes that weighted iterations could nevertheless potentially improve PhaseCut performance.
  • 4.6. Complexity Comparisons.: First-order solvers reduce dimension dependence for both PhaseCut and PhaseLift, but penalized formulations increase precision dependence from log(1/ǫ) to 1/ǫ.
  • 4.6. Complexity Comparisons.: Block coordinate descent has substantially lower iteration complexity and linear convergence, although the number of iterations lacks fully explicit bounds.The available bound has a constant depending on n that cannot be quantified explicitly.
  • 4.6. Complexity Comparisons.: PhaseCut’s singleton constraint matrices enable lower complexity than PhaseLift when using interior-point solvers for small target precision ǫ.For larger ǫ, first-order solvers or block coordinate descent make the complexity difference less significant.
  • 4.6. Complexity Comparisons.: If a relaxation returns a non-rank-one matrix, a leading eigenvector provides an approximate phase-recovery solution that can be refined with Gerchberg-Saxton.The PhaseCut and PhaseLift approximations use different formulas before refinement.

4.7. Greedy Refinement.

PhaseLift’s trace minimization seeks minimum-ℓ2-norm signals satisfying modulus constraints, while sparsity can be incorporated when prior knowledge indicates a sparse signal.

  • 4.7. Greedy Refinement.: PhaseLift trace minimization selects signals matching modulus constraints while minimizing their ℓ2 norm.
  • 4.7. Greedy Refinement.: When the target signal is known to be sparse, sparsity can be imposed through approaches studied in prior work.The passage characterizes sparsity through a small Card(x).

4.8. Sparsity.

The sparsity formulation introduces nullspace variables and an ℓ1 penalty, while PhaseCut imposes unit-modulus diagonal constraints in a semidefinite variable; for injective A, sparsity becomes an ℓ1 penalty on PhaseCut.

  • 4.8. Sparsity.: For n ≤ p, feasible signals are parameterized by a pseudoinverse term plus a basis-weighted nullspace variable.The reconstruction formulation uses x = A† diag(b)u + Fv.
  • 4.8. Sparsity.: The relaxed sparsity formulation uses a semidefinite variable U with positive-semidefinite structure and unit-modulus diagonal constraints.
  • 4.8. Sparsity.: The test signals include Gaussian white noise, sums of six random-frequency sinusoids, and image scan-lines.
  • 4.8. Sparsity.: When n > p and A is injective, the nullspace term disappears and sparsity amounts to adding an ℓ1 penalty to PhaseCut.

5. NUMERICAL RESULTS

Numerical experiments compare PhaseCut with PhaseLift, Weak PhaseLift, and Gerchberg–Saxton across Fourier, random-filter, wavelet, and noisy recovery settings. PhaseCut achieves exact recovery in several tested settings, while performance depends on instability, sparsity, noise, and solver convergence.

  • Oversampled Fourier Transform: For oversampled Fourier recovery, intrinsic instability makes all algorithms perform similarly, with perfect reconstruction below 5%.The average signal error on non-perfectly reconstructed signals is of order one, despite smaller coefficient-amplitude errors.
  • Multiple Random Illumination Filters: With four Gaussian random filters, PhaseCut achieves perfect recovery in all experiments, matching PhaseLift despite both relaxations being only almost rank one.Their dominant eigenvalue exceeds the others by roughly a factor of 5 to 10, and Gerchberg–Saxton refinement then converges to the signal.
  • Wavelet Transform: PhaseLift reconstructs 62% of wavelet-modulus test signals, with rates of 27%, 60%, and 99% for Gaussian noises, sinusoids, and image scan-lines.The variation is attributed to the proportion of wavelet coefficients with negligible amplitudes.
  • Wavelet Transform: PhaseCut exactly reconstructs all real-part wavelet test signals, while Gerchberg–Saxton reconstructs none from random initialization.PhaseCut’s recovered matrix is always rank one, whereas PhaseLift’s lower observed rate is attributed to insufficient first-order convergence at the required precision.
  • Wavelet Transform: Figure 3 shows similar measurement thresholds for PhaseLift and Weak PhaseLift: about 2.5–2.7p for reconstruction and 4.5–4.6p for rank-one exactness.The corresponding thresholds are n = 155 and 285 for PhaseLift, versus n = 170 and 295 for Weak PhaseLift.
  • Reconstruction in the Presence of Noise: Under noise, PhaseCut is stable to roughly 5–10% in wavelet recovery and performs similarly to PhaseLift for Gaussian random illumination filters up to 20% noise.For non-sparse measurements, both algorithms have relative error approximately 7∥bnoise∥2/∥Ax∥2; sparsity makes PhaseLift less stable.

APPENDIX A. TECHNICAL LEMMAS

Appendix A establishes technical lemmas used in Theorem 4.7, relating PhaseCut quantities to PhaseLift quantities through range decompositions and matrix inequalities.

  • Technical lemmas: The appendix states two technical lemmas under Theorem 4.7’s assumptions and notations.These lemmas are introduced as ingredients for the theorem’s proof.
  • Matrix inequality: The argument applies the Cauchy–Schwarz inequality to a positive matrix and uses a Hermitian basis diagonalizing V_PC.The basis combines vectors from range(A) and its orthogonal complement.
  • Feasible-set relation: The proof constructs V=(b × u)(b × u)∗ and relates PhaseCut trace expressions to distances from the feasible set F.The construction uses a phase vector u satisfying |u_i|=1 and (Ax_0)_i=u_i|Ax_0|_i.
  • Norm bound: The appendix derives the bound ∥b_n,PL∥2 ≤ 2∥b_n,PC∥.This is stated as Lemma A.2 under Theorem 4.7’s assumptions and notation.
  • Range decomposition: The proof decomposes each canonical basis vector into components in range(A) and its orthogonal complement.This decomposition is used to analyze the relevant quadratic forms.
Loading 1206.0102v3…