PaperlayerView exact revision on arXiv

Source-linked AI summary

Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation

Sohail Bahmani, Justin Romberg

arXiv:1610.04210v2cs.ITcs.LGmath.FAmath.ITmath.OCstat.ML

TL;DR

Phase retrieval methods based on lifting and semidefinite programming can be computationally prohibitive, while non-convex alternatives have different limitations. This paper proposes a signal-domain convex relaxation using slab constraints and an anchor, and shows that random measurements yield high-probability accurate recovery under its geometric certificate. Its stated analysis assumes a unit-norm target and bounded nonnegative noise.

  • Problem

    SDP-based phase retrieval methods can be computationally prohibitive, motivating scalable approaches that retain provable accuracy.

    Source: §1 · p. 1

  • Method

    The method relaxes phaseless equations into symmetric slab constraints and uses a convex program to select an extreme point aligned with an anchor.

    Source: §1 · p. 2

  • Results

    For random measurements, the geometric success conditions hold with high probability and the estimator accurately recovers the signal.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The signal-domain convex relaxation offers a scalable alternative to SDP-based methods while preserving a high-probability recovery guarantee for random measurements.

    Source: §1 · pp. 2–3

    The theoretical analysis assumes a unit-norm target and nonnegative noise bounded by ∥ξ∥∞≤η^-1.

    Source: §3 · p. 7

Abstract

from arXiv · show

We propose a flexible convex relaxation for the phase retrieval problem that operates in the natural domain of the signal. Therefore, we avoid the prohibitive computational cost associated with "lifting" and semidefinite programming (SDP) in methods such as PhaseLift and compete with recently developed non-convex techniques for phase retrieval. We relax the quadratic equations for phaseless measurements to inequality constraints each of which representing a symmetric "slab". Through a simple convex program, our proposed estimator finds an extreme point of the intersection of these slabs that is best aligned with a given anchor vector. We characterize geometric conditions that certify success of the proposed estimator. Furthermore, using classic results in statistical learning theory, we show that for random measurements the geometric certificates hold with high probability at an optimal sample complexity. Phase transition of our estimator is evaluated through simulations. Our numerical experiments also suggest that the proposed method can solve phase retrieval problems with coded diffraction measurements as well.

1 Introduction

The paper proposes a scalable convex relaxation for phase retrieval in the signal domain, using slab constraints and an anchor to select a feasible extreme point. It connects a geometric success certificate to statistical-learning results for high-probability recovery under random measurements.

1 Introduction

  • The proposed convex relaxation operates in the signal domain, avoiding SDP's scalability drawback while retaining convex optimization's flexibility.The authors contrast it with non-convex methods that operate in the natural signal domain and have better scalability than SDP-based approaches.Source: §1 · pp. 1–2
  • The method replaces each phaseless measurement equation with a symmetric slab and maximizes alignment with an anchor over their intersection.In the noiseless regime, the target is an extreme point; the anchor defines a tangent hyperplane intended to distinguish it from other extreme points.Source: §1 · p. 2
  • A geometric condition from Lemma 2 suffices for accurate estimation, and random measurements satisfy the relevant certificate with high probability through statistical-learning results.The certificate is interpreted using the non-existence of a particularly constrained halfspace containing specified measurement-related points.Source: §1 · p. 3

1.1 Choosing the anchor vector

  • Two anchor scenarios are discussed: a constant vector for real non-negative signals and a principal eigenvector computed from random measurements.For the non-negative-signal scenario, the target must have at least δ^2N non-zero entries; the random-measurement scenario uses a principal eigenvector strategy previously used for Wirtinger Flow initialization.Source: §1.1 · p. 4

1.2 Related work

  • Prior SDP relaxations can achieve accurate estimates at optimal sample complexity for certain random models, but become computationally prohibitive at medium to large scale.The paper also contrasts its analysis with Wirtinger Flow, describing the proposed method as having low computational cost, no tuning parameters, and robustness to a broader set of measurement distributions.Source: §1.2 · pp. 4–5

1.3 Variations and Extensions

  • The authors identify gross-noise modeling as potentially pessimistic and suggest noise regularization, while coded-diffraction experiments suggest good performance on structured measurements.Extending the theory to blockwise-independent measurements may require more sophisticated empirical-process tools; sparsity-inducing ℓ1 regularization is another proposed extension.Source: §1.3 · pp. 5–6

2 Numerical experiments

The experiments evaluate the estimator on synthetic noisy measurements and a large coded-diffraction image. The reported Persian Leopard reconstruction has relative error 8.2 × 10−8.

  • Figure 2 reports median and 0.9-quantile relative error over 100 algorithm trials for sampling ratios M/N from 2 to 17, showing noise-level effects for both considered noise models.Source: §2 · p. 6
  • With 20 coded diffraction patterns (M ≈ 2.5 × 10^7), the 960 × 1280 Persian Leopard reconstruction reached relative error 8.2 × 10−8.Source: Figure 3 · p. 7, §2 · p. 7

3 Theoretical Analysis

The analysis gives geometric conditions for the convex estimator to recover the signal accurately, then establishes a high-probability guarantee for random measurements. It explains the geometry through intersecting complex slabs and uses statistical-learning tools to analyze random measurements.

3 Theoretical Analysis

  • The analysis normalizes the signal and phase, then establishes a geometric condition sufficient for accurate estimation by the convex program.It assumes a unit-norm signal and that a0*x⋆ is positive real, since any point in the phase-equivalence class is a valid target.Source: §3 · p. 7

3.1 Geometry of intersecting slabs

  • The feasible set is an intersection of symmetric complex slabs, and the linear objective selects an extreme point aligned with the anchor.The geometric argument identifies the anchor-normal hyperplane through the target as tangent to the feasible set; a sufficient condition rules out solutions too far from the target.Source: §3.1 · p. 8

3.2 Guarantees for random measurements

  • Under the stated assumptions, Theorem 1 gives a high-probability guarantee for the estimate from i.i.d. random measurements.The theorem setup assumes a unit-norm signal, bounded non-negative noise, an anchor satisfying (2), and random measurement vectors obeying the stated distributional condition.Source: §3.2 · p. 10

A Tools from statistical learning theory

This appendix recalls statistical-learning concepts used in the analysis, including shatter coefficients, VC dimension, and classic results for classes of binary functions.

A Tools from statistical learning theory

  • The shatter coefficient counts the largest number of binary patterns a function class can induce on n points.The appendix also calls it the growth function.Source: A Tools from statistical learning theory · p. 13
  • The VC dimension is the largest n for which the shatter coefficient equals 2^n, or equivalently, the largest number of points the class can shatter.The appendix notes that the VC dimension is infinite if every n-point set can be shattered.Source: A Tools from statistical learning theory · pp. 13–14
  • The appendix states classic results for binary-function classes, including a theorem attributed to Vapnik and Chervonenkis.It also cites the VC-dimension bound of Vapnik and Chervonenkis, Sauer, and Shelah.Source: A Tools from statistical learning theory · p. 14

B Auxiliary Lemma

The auxiliary lemma studies a probability involving independent Rayleigh and normal variables and derives an expression for it using the normal cumulative distribution function.

B Auxiliary Lemma

  • The lemma considers independent Rayleigh(1) and Normal(0, 1) random variables.The supplied passage identifies these as v and g.Source: B Auxiliary Lemma · p. 14
  • For F(β), the proof writes the probability as an expectation involving the normal cumulative distribution function Φ.It defines F(β) using the event αv + βv−1 > γ.Source: B Auxiliary Lemma · p. 14
  • The derivation differentiates F using Leibniz’s rule and simplifies the result using F(0).The proof applies Leibniz’s rule again and then substitutes F(0) into F(β).Source: B Auxiliary Lemma · pp. 14–15
Loading 1610.04210v2…