PaperlayerView exact revision on arXiv

Source-linked AI summary

PhaseMax: Convex Phase Retrieval via Basis Pursuit

Tom Goldstein, Christoph Studer

arXiv:1610.07531v3cs.ITmath.OC

TL;DR

Phase retrieval asks how to recover real- or complex-valued signals from magnitude-only measurements, while existing convex approaches use higher-dimensional lifting. The paper introduces PhaseMax, a non-lifting convex method whose dual is Basis Pursuit, and develops sharp recovery-probability bounds and noise-accuracy analysis across measurement settings. Its simulations demonstrate sharp guarantees and characterize practical efficacy and limits.

  • Problem

    Phase retrieval seeks recovery of real- or complex-valued signals from magnitude-only measurements, while semidefinite convex relaxations require lifting to a higher-dimensional space.

  • Method

    PhaseMax maximizes alignment with an approximation vector under convex measurement constraints in the original signal dimension, with Basis Pursuit as its dual.

  • Results

    The paper derives sharp lower bounds on PhaseMax success probability across random measurement ensembles and characterizes measurement-noise effects on solution accuracy.

  • Takeaways & Limitations

    PhaseMax provides a convex, non-lifting phase-retrieval approach whose guarantees are demonstrated to be sharp in simulations and whose dual enables Basis Pursuit solvers.

Abstract

from arXiv · show

We consider the recovery of a (real- or complex-valued) signal from magnitude-only measurements, known as phase retrieval. We formulate phase retrieval as a convex optimization problem, which we call PhaseMax. Unlike other convex methods that use semidefinite relaxation and lift the phase retrieval problem to a higher dimension, PhaseMax is a "non-lifting" relaxation that operates in the original signal dimension. We show that the dual problem to PhaseMax is Basis Pursuit, which implies that phase retrieval can be performed using algorithms initially designed for sparse signal recovery. We develop sharp lower bounds on the success probability of PhaseMax for a broad range of random measurement ensembles, and we analyze the impact of measurement noise on the solution accuracy. We use numerical results to demonstrate the accuracy of our recovery guarantees, and we showcase the efficacy and limits of PhaseMax in practice.

I. INTRODUCTION

PhaseMax is a non-lifting convex formulation for recovering real- or complex-valued signals from magnitude-only measurements. Its guarantees relate recovery probability to measurement count and initializer accuracy, while its dual Basis Pursuit formulation connects phase retrieval with sparse signal recovery.

  • Problem: Phase retrieval recovers an n-dimensional real- or complex-valued signal from squared-magnitude, noisy measurements.The measurements use known vectors and additive noise.
  • PhaseMax formulation: PhaseMax maximizes alignment with an approximation vector subject to convex magnitude constraints in the original signal dimension.The approximation vector may be produced by an algorithm or chosen at random.
  • Recovery guarantees: For complex-valued signals with uniformly sampled measurement vectors, PhaseMax succeeds with non-zero probability whenever αm > 4n.Equivalently, m > 4n/α with α > 0.
  • Recovery guarantees: For any approximation vector less than π/2 from the true signal, increasing m can make the success probability arbitrarily close to one.The paper reports that these guarantees are sharp and accurately predict practical performance.
  • Basis Pursuit connection: The dual of PhaseMax is Basis Pursuit, whose solution phases recover the phase information lost in the magnitude measurements.This connection allows Basis Pursuit solvers to recover signals from phase-less measurements.
  • Contributions and related work: PhaseMax avoids the higher-dimensional lifting required by semidefinite relaxations, while the paper extends analysis across random ensembles, noise, and initializer choices.The authors also describe later work on sparse and corruption-robust variants, BranchHull, and asymptotic analyses.

D. Contributions and Paper Outline

The paper develops PhaseMax as a convex, non-lifting phase-retrieval method and establishes deterministic and probabilistic recovery guarantees using geometric probability.

  • Recovery guarantees: The resulting analysis provides sharp lower bounds for real- and complex-valued noiseless systems, with extensions to broader ensembles and noisy measurements discussed in the paper.
  • Uniqueness condition: The measurement constraints admit phase-rotated solutions, while PhaseMax selects the solution aligned with the approximation vector.
  • Uniqueness condition: In the noiseless case, a deterministic condition guarantees that the true signal is the unique maximizer of PhaseMax.
  • Geometric probability: Geometric-probability tools analyze when random spherical caps cover the directions relevant to PhaseMax recovery.
  • Geometric probability: The sphere-covering probability can be expressed through the probability of obtaining n or more heads when flipping m_A − 1 fair coins.

IV. RECOVERY GUARANTEES

The paper uses the uniqueness condition and geometric-probability tools to derive sharp lower bounds for noiseless PhaseMax recovery in real and complex systems.

  • The uniqueness condition from Theorem 2 supplies the deterministic basis for the recovery analysis.
  • Geometric-probability tools are used to develop the success-probability bounds.
  • The stated bounds concern noiseless real- and complex-valued systems, while the noisy case is deferred to Section V-B.

A. The Real Case

For real-valued systems, aligned measurement vectors and spherical geometry yield a condition for exact reconstruction and a lower bound on PhaseMax success probability.

  • Aligned measurement vectors are formed as ˜a_i = phase(⟨a_i, x0⟩)a_i and satisfy ⟨˜a_i, x0⟩≥0.
  • The true vector x0 is the unique maximizer of PhaseMax when the stated geometric condition on the aligned vectors holds.
  • The lower-bound derivation applies the geometric uniqueness condition to the independently sampled aligned measurements.
  • For uniformly sampled real measurement vectors, the recovery probability p_R(m, n) is bounded from below by Theorem 3.

B. The Complex Case

For complex-valued phase retrieval, PhaseMax succeeds when measurement-induced ascent directions cover the relevant aligned descent directions. The resulting recovery guarantees become arbitrarily strong with sufficiently many measurements when the approximation vector is not orthogonal to the true signal.

  • Recovery guarantee: Theorem 1 gives a lower bound on the probability that PhaseMax exactly recovers a complex signal from uniformly sampled noiseless measurements.The bound is expressed through the probability that aligned measurement vectors cover an appropriate spherical cap.
  • Geometric condition: The true signal is the unique PhaseMax maximizer when every unit aligned direction satisfies the theorem’s measurement inequality.This condition is established through the coverage of aligned measurement-vector caps.
  • Proof geometry: The complex proof projects descent directions onto the real-orthogonal subspace of the true signal and transfers cap coverage from that subspace.The projection δ′ preserves the relevant alignment properties and links the complex geometry to a real sphere.
  • Proof geometry: The coverage probability is bounded using spherical geometry, with the complex problem mapped to a sphere of dimension related to 2n−2.The analysis uses a slightly weaker bound based on pcover(m, 2n; x0, ˆx).
  • Scope of guarantee: Exact recovery is guaranteed for sufficiently large m when angle(x0, ˆx) < π/2.When angle(x0, ˆx) > π/2, the theorems instead guarantee convergence to −x0; failure for large m is confined to the orthogonal case.

V. GENERALIZATIONS

The recovery guarantees extend beyond uniformly sampled unit-sphere measurements. Rotationally symmetric ensembles retain the same guarantees after normalization, while general non-uniform sampling can require more measurements.

  • Rotationally symmetric ensembles: The noiseless recovery theory extends from uniform unit-sphere sampling to all rotationally symmetric measurement distributions.Normalizing each measurement vector preserves the feasible set and the PhaseMax solution.
  • Rotationally symmetric ensembles: Theorem 1 and Theorem 3 therefore apply to i.i.d. multivariate Gaussian measurement vectors.The Gaussian distribution is rotationally symmetric, so normalization makes it equivalent to uniform sphere sampling.
  • Non-uniform ensembles: Non-spherically symmetric distributions remain analyzable, but the corresponding guarantees require a larger number of measurements.Theorem 4 develops the analogous noiseless complex-case result using a lower bound on the sampling density.
  • Non-uniform ensembles: For non-uniform sampling, mD measurements guarantee at least the recovery probability of mU=⌊mDsnℓD⌋ uniform measurements when αmU > 4n and ℓD > 0.The comparison follows by lower-bounding the sampling density and matching the non-uniform model to a uniform model with fewer effective measurements.
  • Non-uniform ensembles: The non-uniform comparison is obtained by relating the densities of uniform and distribution-D measurement ensembles.The probability of exact recovery under the non-uniform model is at least the uniform-model probability when the density ratio is at least one.

B. Noisy Measurements

The noisy-measurement analysis bounds PhaseMax reconstruction error through the geometry of aligned measurement caps. The guarantees depend on relative noise, approximation-vector angle, measurement count, and feasibility conditions.

  • Geometric error bound: Theorem 5 reduces noisy recovery to a geometric condition: if aligned caps cover the descent-direction set, the recovery error is bounded by ε.The cap angle is θ = arccos(r/2ε), with ε > r/2 and r the maximum relative noise.
  • Geometric error bound: Non-negative noise keeps the true signal feasible, which implies that the error vector has nonnegative objective alignment.The reformulated constraints expose Δ = x⋆ − x0 and support the cap-based error argument.
  • Probabilistic guarantee: Theorem 6 gives a probabilistic error guarantee for uniformly sampled complex measurements using φ = arccos(r/2ε) − angle(x0, ˆx).The result assumes ε > r/2 and applies when n ≥ 5 and m > 4n.
  • Probabilistic guarantee: The probability of the noisy recovery bound is controlled by spherical cap coverage of the aligned measurement vectors.The proof relates the relevant half-sphere coverage to pcover(m, 2n, φ).
  • Signed noise: For noise with both signs, a shrink-factor transformation converts the problem to one with non-negative noise before applying Theorem 6.The transformed solution is first bounded relative to sx0, then related back to the original signal.

VI. HOW TO COMPUTE APPROXIMATION VECTORS?

Approximation vectors, also called initialization or anchor vectors, can be generated by several spectral, geometric, or least-squares procedures. The paper also considers random approximation vectors and more sophisticated initializers.

  • Approximation-vector methods: Approximation vectors can be computed using truncated spectral, optimized spectral, Null, orthogonality-promoting, or least-squares methods.These vectors serve as initialization or anchor vectors for PhaseMax.
  • Random initialization: The paper studies whether randomly generated approximation vectors can support high-probability PhaseMax recovery with sufficiently many measurements.

A. Random Initialization

Random approximation vectors can enable PhaseMax recovery with high probability, but require O(n^3/2) measurements, making stronger initialization potentially more practical.

  • A. Random Initialization: Random approximation vectors are drawn uniformly from the unit sphere, and PhaseMax depends on their alignment with the unknown signal.The analysis uses the magnitude of the inner product because a negative inner product leads PhaseMax to recover −x0 instead.
  • A. Random Initialization: The expected magnitude of the inner product between independent random unit vectors is used to bound the approximation accuracy α.The derivation analyzes the cosine distance distribution through beta- and Gamma-function identities for real and complex vectors.
  • A. Random Initialization: For real-valued signals, exact reconstruction succeeds with probability approaching 1 rapidly when m > cn^3/2 for any c > π^3/2.This conclusion applies to an average randomly generated approximation vector satisfying the stated accuracy condition.
  • A. Random Initialization: Random initialization requires O(n^3/2) measurements, compared with O(n) for algorithms using other initialization methods.The paper therefore suggests that PhaseMax may be more practical with approximation vectors produced by more sophisticated initializers.

B. Spectral Initializers

Spectral initializers provide approximation vectors that allow PhaseMax to achieve linear measurement scaling under Gaussian measurements, with theory requiring roughly 5.5n measurements.

  • B. Spectral Initializers: Spectral initializers were developed to compute approximation vectors with strong theoretical properties for phase retrieval.The paper cites prior analyses of this initializer class, including an optimal initializer for a class of problems containing phase retrieval.
  • B. Spectral Initializers: With m = δn Gaussian measurement vectors, spectral initializers achieve a limiting positive accuracy parameter α⋆.The stated condition is lim_n→∞ angle(ˆx, x0) > ϵ for some positive ϵ, equivalently α⋆ > 0.
  • B. Spectral Initializers: Combining spectral initialization with the recovery theorem yields high-probability PhaseMax success using m > n/α⋆ recovery measurements, which is linear in n.The total count exceeds n/α⋆ + δn when initialization and recovery measurements are combined, assuming independence from the measurement vectors.
  • B. Spectral Initializers: PhaseMax requires roughly m = 5.5n noiseless Gaussian measurements in theory and somewhat fewer in practice.The constants in the underlying bounds were approximated using stochastic numerical methods rather than obtained exactly by analysis.
  • B. Spectral Initializers: PhaseMax has the same sample complexity as PhaseLift, TWF, and TAW when paired with the truncated spectral initializer, while its guarantees explicitly depend on α.Unlike the other methods’ generally large constants, the PhaseMax guarantees contain no unspecified constants and are described as sharp.

B. Tightness of Recovery Guarantees

Experiments show that PhaseMax’s theoretical guarantees closely track empirical success, while practical comparisons reveal a trade-off: it needs more measurements than leading non-convex methods but retains convexity, original-dimension operation, and sharp guarantees.

  • Tightness of Recovery Guarantees: Theoretical lower bounds accurately predict empirical PhaseMax success, with especially tight agreement for larger dimensions and larger approximation angles.Experiments also show a progressively sharper failure-to-success phase transition as dimension increases.
  • Tightness of Recovery Guarantees: A spectral initializer achieves squared cosine similarity above 0.6 when 2n measurements are used for spectral estimation.The PhaseMax analysis requires initializer and recovery measurements to be statistically independent.
  • Comparisons Using Synthetic Data: PhaseMax requires larger oversampling ratios than comparable non-convex methods because its truncated spectral initializer needs ratios of about six or higher.This initializer accuracy is required to produce approximation vectors that enable PhaseMax to succeed.
  • Comparisons Using Empirical Data: On empirical diffusive-medium data, Gerchberg-Saxton has the lowest measurement error, while PhaseMax produces visually comparable reconstructions with slightly higher relative error.The comparison uses two 64 × 64 masks and reports relative measurement error for each method.
  • Advantages of PhaseMax: PhaseMax does not achieve exact recovery at the lowest measurement count, but is convex, non-lifting, compatible with Basis Pursuit solvers, and supported by sharp performance guarantees.Its convexity also supports extensions incorporating sparse, total-variation, or bounded-infinity-norm priors.
  • Conclusions: Future work includes efficient large-scale solvers for PhaseMax or PhaseLamp and accurate analysis of more general noise models.These directions mark computational and modeling boundaries identified by the authors.

APPENDIX A PROOF OF LEMMA 1

The appendix proves a sphere-covering bound by induction, reducing the effect of each added hyperplane to the regions it intersects. It then simplifies a general covering theorem into a more intuitive lower bound under explicit dimensional and measurement conditions.

  • Proof of Lemma 1: The proof inductively counts regions formed by slicing an n-dimensional sphere with planes, using base cases r(n,1)=2 and r(2,k)=2k.Adding a plane increases the region count by the number of existing regions intersected by that plane.
  • Proof of Lemma 1: Lemma 4 is derived as a direct corollary of a result by Bürgisser, Cucker, and Lotz.The appendix points to the cited theorem for the complete proof and constant bound.
  • Proof of Lemma 1: Lemma 4 provides a weaker but more intuitive lower bound for sphere coverage when n≥9 and m>2n.The simplification uses Hoeffding’s inequality and subsequent integral bounds.
  • Proof of Lemma 1: The remaining derivation converts integral terms into exponentials, applies Cauchy–Schwarz, and substitutes ε=cos(φ) to obtain the result.These steps simplify the covering bound into the stated form.
Loading 1610.07531v3…