PaperlayerView exact revision on arXiv

Source-linked AI summary

A Geometric Analysis of Phase Retrieval

Ju Sun, Qing Qu, John Wright

arXiv:1602.06664v3cs.ITmath.OCstat.ML

TL;DR

The paper asks whether complex signals can be recovered from magnitude-only measurements and why nonconvex heuristics succeed despite limited theoretical explanation. It analyzes a natural least-squares formulation under i.i.d. complex Gaussian measurements, proving benign geometry and studying a second-order trust-region method. With m ≥ Cn log^3 n, the objective has no spurious local minimizers, and recovery is possible efficiently without special initialization.

  • Problem

    GPR asks whether an unknown complex vector can be recovered from magnitude-only projections, up to an unavoidable global phase, while nonconvex heuristics lack clear theoretical explanations.

  • Method

    The paper performs a global geometric analysis of a natural least-squares formulation under i.i.d. complex Gaussian measurements and analyzes a modified second-order trust-region algorithm.

  • Results

    When m ≥ Cn log^3 n, with probability at least 1−cm^-1, the objective has no spurious local minimizers; its global minimizers are the target and phase-equivalent copies, with negative curvature at saddles.

  • Takeaways & Limitations

    The benign geometry allows efficient iterative methods to find a global minimizer without special initialization, including the analyzed trust-region method.

  • Takeaways & Limitations

    The analysis is for Gaussian measurements, which the authors note are not practical, and its heavy-tailed fourth-order objective creates technical sample-complexity challenges.

Abstract

from arXiv · show

Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of $m$ measurements, $y_k = |\mathbf a_k^* \mathbf x|$ for $k = 1, \dots, m$, is it possible to recover $\mathbf x \in \mathbb{C}^n$ (i.e., length-$n$ complex vector)? This **generalized phase retrieval** (GPR) problem is a fundamental task in various disciplines, and has been the subject of much recent investigation. Natural nonconvex heuristics often work remarkably well for GPR in practice, but lack clear theoretical explanations. In this paper, we take a step towards bridging this gap. We prove that when the measurement vectors $\mathbf a_k$'s are generic (i.i.d. complex Gaussian) and the number of measurements is large enough ($m \ge C n \log^3 n$), with high probability, a natural least-squares formulation for GPR has the following benign geometric structure: (1) there are no spurious local minimizers, and all global minimizers are equal to the target signal $\mathbf x$, up to a global phase; and (2) the objective function has a negative curvature around each saddle point. This structure allows a number of iterative optimization methods to efficiently find a global minimizer, without special initialization. To corroborate the claim, we describe and analyze a second-order trust-region algorithm.

1 Introduction

Generalized phase retrieval asks whether a complex signal can be recovered from magnitude-only measurements despite global-phase ambiguity. The paper explains why nonconvex heuristics work by proving benign global geometry and analyzing an initialization-free trust-region method.

  • Problem and motivation: GPR seeks to recover a complex vector x from magnitudes of projections onto known vectors, necessarily only up to a global phase.The problem connects to Fourier phase retrieval and applications including crystallography, optical imaging, astronomy, microscopy, acoustics, and quantum information.
  • Problem and motivation: The natural least-squares objective is a nonconvex fourth-order polynomial, making recovery without initialization guarantees non-obvious.Earlier provable nonconvex approaches relied on careful initialization near the unknown target.
  • Algorithm and implications: The analysis explains the observed success of nonconvex heuristics and extends global geometric analysis to a problem with heavy-tailed objectives and important sample-complexity requirements.The authors identify connections to analogous geometric analyses in dictionary learning and other nonconvex problems.
  • Geometric analysis: The paper proves that, when m ≥ Cn log^3 n, the objective has no spurious local minimizers and has negative curvature at saddle points with high probability.Its only global minimizers are the target and its global-phase copies; near them, the objective is strongly convex orthogonal to the flat phase direction.
  • Geometric analysis: The benign geometry supports efficient iterative recovery from arbitrary initialization, provided the method can escape saddle points.The key requirement is a direction of strictly negative Hessian curvature at saddles.
  • Algorithm and implications: The analyzed second-order trust-region algorithm reaches a global minimizer in polynomial time and achieves quadratic convergence near global minimizers.Its steps are constrained to be orthogonal to the trivial phase direction, which improves practical convergence and supports the quadratic rate.

2 The Geometry of the Objective Function

The paper characterizes a benign finite-sample geometry for the phase-retrieval objective: every point has either large gradient, negative curvature, or lies near the target set, where restricted strong convexity holds. The analysis extends the corresponding asymptotic landscape and supports efficient second-order optimization.

  • 2.1 A Glimpse of the Asymptotic Function Landscape: The asymptotic objective has only the origin, the target circle X, and a saddle-point set S as critical points.The origin is a local maximizer, X is the local/global minimizer set, and S consists of saddle points.
  • 2.1 A Glimpse of the Asymptotic Function Landscape: All asymptotic critical points outside X have a direction of strict negative curvature, including the origin and saddle points.At points in S, curvature is positive in another direction, confirming their saddle structure.
  • 2.2 The Finite-Sample Landscape: The finite-sample space C^n divides into regions with negative curvature, strong gradient, or restricted strong convexity near the target set.This whole-space characterization provides quantitative controls near critical points for algorithm design and analysis.
  • 2.3 Key Steps in the Geometric Analysis: The proof must control heavy-tailed random variables arising from the fourth-order polynomial objective; uniform closeness to expectations would otherwise require m ≥ Cn^2.The analysis uses more refined concentration arguments rather than directly imposing this wasteful sample size.
  • 2.2 The Finite-Sample Landscape: When m ≥ Cn log^3 n, with probability at least 1 − cm^-1, the objective has no spurious local minimizers and only the target set X as local/global minimizers.The finite-sample geometry preserves the important qualitative features of the large-sample landscape.
  • 2.3 Key Steps in the Geometric Analysis: Near X, the objective is strongly convex in directions orthogonal to the phase circle, enabling quadratic convergence for the modified trust-region method.The stronger restricted strong convexity controls all directions orthogonal to the trivial flat direction in a neighborhood of X.

3 Optimization by Trust-Region Method (TRM)

The paper develops a modified second-order trust-region method that moves orthogonally to the phase-invariant direction and analyzes its global convergence. Under sufficient measurements, the method reaches the target set from arbitrary initialization and converges quadratically near it.

  • Modified trust-region algorithm: The method constrains each step to be geometrically orthogonal to the phase direction, removing movement along the circle of equivalent solutions.This modification is important for practical speed and the quadratic asymptotic convergence guarantee.
  • Modified trust-region algorithm: The trust-region method constructs quadratic local models, minimizes them within a trust region, and updates the iterate by the resulting step.The trust-region subproblem is formed from a second-order Taylor approximation of the objective.
  • Modified trust-region algorithm: The modified complex trust-region subproblem reduces to a classical real trust-region problem in 2n − 1 variables and can be solved in polynomial time.The reduction uses an orthonormal basis for the real subspace orthogonal to the trivial direction.
  • Trust-region subproblem: When the trust-region matrix is positive definite and the unconstrained solution is feasible, the unique interior minimizer can be found with O(d^3) arithmetic complexity.The procedure tests positive definiteness, solves Aw⋆ = −b, and checks feasibility.
  • Convergence analysis: If the gradient is large or the Hessian has sufficiently negative curvature, the trust-region step decreases the objective by a uniform amount.This descent argument underpins the iteration-complexity analysis.
  • Convergence analysis: For m ≥ Cn log^3 n, the trust-region algorithm reaches an ε-close solution from arbitrary initialization with high probability and converges quadratically near the target set.The local quadratic result follows after the method begins taking unconstrained steps in the target neighborhood.

4 Numerical Simulations

The numerical experiments test measurement requirements and compare the trust-region method with gradient descent. They use modified, dynamically sized numerical solvers while highlighting both empirical recovery behavior and practical limitations of the idealized analysis.

  • Experimental implementation: The analysis assumes exact trust-region subproblem solutions and a sufficiently small fixed step size, unlike practical implementations.In practice, subproblems are approximate and step sizes are adjusted by backtracking.
  • Experimental implementation: The practical implementation uses truncated conjugate gradients, dynamically adjusts the step size, and explicitly follows negative-curvature directions near saddles.This differs from the exact, fixed-step solver assumed in the convergence analysis.
  • Measurement experiments: For n = 1,000, each measurement setting is tested on a fixed instance with 25 independently randomized initializations.Recovery probability is estimated from these 25 repetitions.
  • Measurement experiments: Empirically, m = 7n samples appears sufficient for the geometric property, whereas m = 6n is insufficient in the tested setting.The experiment uses recovery probability as an empirical test for spurious local minimizers and the desired landscape.
  • TRM versus gradient descent: On the campus-image experiment, TRM reaches εRel ≤ 10^-4 in about 2600 seconds, while gradient descent reaches εRel ∼ 10^-2 in about 6The comparison uses m = 5n log n complex Gaussian measurements and averages ten trials.

5 Discussion

The discussion presents the geometric characterization as enabling initialization-free recovery, identifies sample-complexity gaps, and outlines limitations from Gaussian measurements and computational storage.

  • Main implications: The paper’s geometric characterization supports a second-order trust-region algorithm that efficiently finds a global minimizer without special initialization.The method is designed around the absence of spurious local minima and the presence of negative curvature at saddles.
  • Sample complexity: The theory requires m ≥ C1n log^3(n) samples, while simulations suggest that C2n log(n) or even C3n may suffice.The discussion identifies closing this gap as an open issue.
  • Measurement models: The analysis applies only to Gaussian measurements, which the authors identify as impractical and call to extend to more practical schemes.The cited discussion specifically motivates extensions beyond the current measurement model.
  • Computational limitations: For the reported experiment, storing all measurement vectors—not the TRM solver—was the main computational limitation.Matrix-free calculations can remove this storage bottleneck for coded diffraction measurements.

6 Proofs of Technical Results for Function Landscape

The technical proofs establish concentration and regularity properties for the objective and its derivatives, then use region-wise geometric arguments to control gradients, curvature, and distance from the target set.

  • Concentration and regularity: The proofs begin with Gaussian expectation identities and concentration bounds for the objective, gradient, Hessian, and related measurement sums.Net arguments, Bernstein-type inequalities, Chebyshev bounds, and union bounds extend pointwise estimates uniformly over vectors.
  • Concentration and regularity: When m is at least on the order of n log n, the analysis obtains high-probability uniform estimates over the relevant complex regions.Several lemmas state probability bounds under conditions such as m ≥ C(δ)n log n.
  • Uniform control: The proof controls approximation errors by discretizing balls and spheres with ε-nets and extending bounds through continuity and Lipschitz estimates.The net radius is chosen in relation to n and log m to preserve uniform control.
  • Geometry near the target: Near the target set, Hessian curvature is controlled in directions orthogonal to the phase orbit, while the phase direction remains the single trivial flat direction.This local curvature property supports the quadratic convergence analysis.
  • Global landscape: Away from the target region, the proof establishes either gradient growth or descent-related inequalities that exclude spurious local minimizers.The regions are combined to cover the ambient space and to show that stationary points outside the target set possess a descent or negative-curvature mechanism.

7 Proofs of Technical Results for Trust-Region Algorithm

The technical proofs establish high-probability bounds for the measurements, gradient, Hessian, and auxiliary radii under linear or logarithmically inflated measurement conditions.

  • Uniform bounds: When m ≥ Cn, Lemma 7.1 provides a uniform high-probability bound for all z,w ∈ C^n.The failure probability is exponentially small in m.
  • Uniform bounds: When m ≥ Cn log n, Lemma 7.2 provides a uniform high-probability bound over every phase ψ ∈ [0, 2π).The stated failure probability combines an inverse-polynomial term with an exponentially decaying term.
  • Radius control: The auxiliary radius satisfies R1 ≤ 30(n log m)1/2∥x∥ with high probability after bounding R0 by 10∥x∥.This estimate is substituted into the preceding bounds to obtain the claimed results.

7.3 Proof of Lemma 3.2

The proof of Lemma 3.2 combines upper and lower bounds derived from earlier lemmas, together with a norm condition that holds with high probability for sufficiently many measurements.

  • Bounding the Hessian-related quantity: The upper-bound argument applies Lemma 7.2 uniformly over z ∈ R′.The passage identifies this as the key step in obtaining the upper bound.
  • Bounding the Hessian-related quantity: The lower bound is reduced to an equivalent inequality for all z ∈ R′ and then obtained using Lemma 3.1 and Lemma 7.2.The proof explicitly combines these two earlier results.
  • Norm conditions: The quantity Lh is bounded by 480(n log m)1/2∥A∥2, while ∥A∥2ℓ1→ℓ2∥x∥ ≥ 150∥x∥ under a high-probability norm condition.The latter condition holds when m ≥ C1n for sufficiently large C1.
  • Feasible direction: The proof also analyzes a feasible direction δ based on xeiφ(z)/∥x∥ and imposes ∆ ≤ ∥x∥2/(400Lh) to obtain the final inequality.The direction is constructed within the feasible trust-region set.

7.6 Proof of Proposition 3.5

The proof of Proposition 3.5 constructs feasible trust-region directions and shows that the objective decreases by a quantitative amount during the resulting iteration.

  • Feasible directions: Vectors of the form tδ are feasible for the trust-region subproblem for t ∈ [0, ∆].This feasibility is used with Lemma A.2 to analyze the objective along the direction.
  • Objective decrease: For points z(r) with ∥z(r)∥ ≥ ∥x∥/2, the directional estimate gives f(z(r)+tδ)−f(z(r)) ≤ −t∥x∥3/2000 + t2Lg.The norm condition follows because the relevant points lie outside the region contained in R1.
  • Objective decrease: Combining the directional decrease with Lemma 3.3 yields f(z(r+1))−f(z(r)) ≤ −∆∥x∥3/4000.The bound also includes the terms ∆2Lg and 2∆3Lh/3 before simplification.
  • Other regions: In another region, the proof lower-bounds ∥h(z)∥ by ∥x∥2/(10Lh) and chooses δ proportional to −h(z(r)).The remaining argument is described as analogous to Proposition 3.5.

7.8 Proof of Proposition 3.7

The proof of Proposition 3.7 analyzes trust-region steps through orthogonal projections, transformed derivatives, and a quadratic approximation based on the Hessian bound.

  • Geometric decomposition: Identifying C^n with R^2n permits orthogonal projection of a vector onto z and its orthogonal complement.These projections define the geometric decomposition used in the proof.
  • Trust-region step: The proof selects a feasible direction proportional to −P(iz(r))⊥∇z(r)f(z(r)) for the trust-region subproblem.The step length is restricted by the trust-region radius and the projected gradient norm.
  • Quadratic model: The local quadratic approximation is bounded using MH and a step size chosen as the minimum of reciprocal curvature-related quantities.The passage introduces MH as defined in Lemma 3.2.
  • Coordinate analysis: An orthogonal basis U and the transformed gradient and Hessian are used to analyze the step in coordinates adapted to the geometry.The transformed gradient is denoted g(z(r)) in the proof.
  • Final bound: The final simplification uses MH ≥ mH and Lemma A.3 to complete the bound.The cited inequalities provide the final control needed by the proposition.

7.9 Proof of Proposition 3.8

The proof analyzes trust-region iterates through orthonormal bases, real embeddings, Taylor bounds, and principal-angle estimates. Under Δ ≤ ∥x∥/10, these estimates control the evolving subspaces.

  • The proof uses U(z) as an orthonormal basis for vectors w satisfying ℑ(w∗z) = 0.
  • The trust-region method supplies an unconstrained optimality condition, which is combined with Taylor’s theorem and Hessian Lipschitzness.
  • The complex bases are converted into real orthonormal matrices V(r) and V(r+1) to compare their subspaces.
  • The largest principal angle is bounded through the corresponding normal vectors of the two subspaces.
  • cos θ1 ≥ 1 − 5/(3∥x∥^2∥ξ⋆∥^2) under the proof’s stated estimates.
  • The final estimates repeatedly use the assumption Δ ≤ ∥x∥/10.

7.10 Proof of Proposition 3.9

The proof establishes that trust-region iterates remain in R′ and that sufficiently small-radius steps become unconstrained. Repeating the argument controls all subsequent steps.

  • The proof first shows that z(r+1) remains in R′.
  • Proposition 3.8 provides estimates used to control the next iterate and the trust-region step.
  • When Δ is sufficiently small, the next transformed trust-region subproblem has a minimizer with norm below Δ.
  • Because the transformed and original step norms agree, the corresponding original step is unconstrained.
  • Repeating the argument implies that all future steps remain constrained within R′.

A Basic Tools and Results

This section collects probabilistic inequalities, Gaussian matrix facts, subspace-angle identities, and Taylor-expansion tools used in the analysis.

  • The appendix states moment and spectral results for complex Gaussian variables and matrices.
  • Integral Taylor formulas and Hessian Lipschitzness control the error of second-order quadratic approximations.
  • Hoeffding- and Bernstein-type inequalities provide concentration tools for independent sub-Gaussian and sub-exponential variables.
  • A lower-tail lemma treats sums of independent copies of a nonnegative random variable with finite second moment.
  • The moment-control Bernstein inequality applies to independent copies of a real-valued variable under factorial moment bounds.
  • For two k-dimensional subspaces, the largest principal angle equals the largest angle between their orthogonal complements.
Loading 1602.06664v3…