Phase Retrieval Under a Generative Prior

Paul Hand; Oscar Leong; Vladislav Voroninski

Source-linked AI summary

Phase Retrieval Under a Generative Prior

Paul Hand, Oscar Leong, Vladislav Voroninski

arXiv:1807.04261v1Jul 11, 2018cs.ITcs.LGmath.OCmath.PR

TL;DR

The paper addresses the measurement inefficiency of sparse phase retrieval, where no known efficient method achieves fewer than O(k^2 log n) generic measurements. It models signals with a deep generative network and optimizes an empirical risk over latent codes, proving favorable global geometry under Gaussian conditions. The resulting framework achieves information-theoretically optimal sample complexity and outperforms sparse phase retrieval methods, while reconstruction accuracy is bounded by generative-model representational error.

Problem
Sparse phase retrieval has no known computationally efficient method succeeding with fewer than O(k^2 log n) generic measurements, above the O(k log n) theoretical optimum.
Method
The paper models signals as outputs of a deep fully connected ReLU generator and recovers the latent code by minimizing an ℓ2 empirical risk.
Results
The objective has favorable global geometry for gradient methods, with recovery possible using O(kd^2 log n) measurements and experiments outperforming sparse phase retrieval methods.
Takeaways & Limitations
Generative priors can impose tighter structure than sparsity while attaining information-theoretically optimal sample complexity for structured phase retrieval.
Takeaways & Limitations
Per-pixel reconstruction accuracy saturates because it is bounded by the generative model’s representational error.

Abstract

from arXiv · show

The phase retrieval problem asks to recover a natural signal $y_0 \in \mathbb{R}^n$ from $m$ quadratic observations, where $m$ is to be minimized. As is common in many imaging problems, natural signals are considered sparse with respect to a known basis, and the generic sparsity prior is enforced via $\ell_1$ regularization. While successful in the realm of linear inverse problems, such $\ell_1$ methods have encountered possibly fundamental limitations, as no computationally efficient algorithm for phase retrieval of a $k$-sparse signal has been proven to succeed with fewer than $O(k^2\log n)$ generic measurements, exceeding the theoretical optimum of $O(k \log n)$. In this paper, we propose a novel framework for phase retrieval by 1) modeling natural signals as being in the range of a deep generative neural network $G : \mathbb{R}^k \rightarrow \mathbb{R}^n$ and 2) enforcing this prior directly by optimizing an empirical risk objective over the domain of the generator. Our formulation has provably favorable global geometry for gradient methods, as soon as $m = O(kd^2\log n)$, where $d$ is the depth of the network. Specifically, when suitable deterministic conditions on the generator and measurement matrix are met, we construct a descent direction for any point outside of a small neighborhood around the unique global minimizer and its negative multiple, and show that such conditions hold with high probability under Gaussian ensembles of multilayer fully-connected generator networks and measurement matrices. This formulation for structured phase retrieval thus has two advantages over sparsity based methods: 1) deep generative priors can more tightly represent natural signals and 2) information theoretically optimal sample complexity. We corroborate these results with experiments showing that exploiting generative models in phase retrieval tasks outperforms sparse phase retrieval methods.

1 Introduction

The paper replaces sparsity-based phase retrieval with a generative prior, optimizing over a neural-network latent code. It establishes favorable gradient geometry and information-theoretically optimal sample complexity under suitable conditions, supported by Gaussian-network analysis and experiments.

Problem and formulation: Phase retrieval recovers signals from phaseless measurements, and this work assumes the signal lies in the range of a generative model.The latent code is recovered first, then mapped through the generator to obtain the signal.
Motivation: ℓ1-based sparse phase retrieval has no known computationally efficient method succeeding below O(k^2 log n) generic measurements, despite an O(k log n) target.This contrasts with the optimal sample complexity achieved by sparsity in linear compressed sensing.
Method: The proposed formulation uses a d-layer fully connected ReLU generator and minimizes an ℓ2 empirical risk over its latent domain.The generator has no bias terms and maps R^k into the signal space.
Theory: m = Ω(kd log(n1 ... nd)) measurements suffice for a descent direction outside neighborhoods of the true code and a negative multiple, under sufficient layer expansiveness.The origin is also a local maximum, and the negative solution scale ρ_d approaches 1 as depth increases.
Theory: The objective has no spurious local minima or saddle points away from neighborhoods of the true solution and its negative multiple.The proof establishes deterministic conditions and then shows Gaussian weights and measurements satisfy them with high probability.
Experiments and implications: Experiments on synthetic and natural signals report recovery with O(kd^2 log n) measurements while outperforming alternative sparse phase retrieval methods.The framework is presented as enabling tighter priors than sparsity and information-theoretically optimal sample complexity.

2 Algorithm

The algorithm uses the generative-prior objective’s landscape to guide gradient descent toward the true latent solution, while explicitly escaping a competing negative-multiple minimum. The generator’s nonnegativity resolves the signal sign ambiguity, and objective comparisons identify the preferred basin.

Landscape: The objective has minima near the true solution x0 and a negative multiple −βx0, but its value is lower near x0.The true solution is the global optimum, whereas the negative multiple creates a competing local minimum.
Generator representation: For each layer, Wi,+,x retains rows active for latent input x and zeros the inactive rows, yielding the generator’s piecewise-linear representation.The resulting active-weight products express G(x) directly for the current latent code.
Gradient method: The method initializes gradient descent at a nonzero latent point, computes a descent direction, and steps in its negative direction.The descent direction is the gradient of the differentiable objective; piecewise linearity permits the broader directional-derivative construction.
Gradient method: Before each update, the algorithm replaces xi by −xi when f(−xi) < f(xi), thereby escaping the negative-multiple region in favor of the lower-valued basin.The comparison is motivated by the lower objective value near the true solution than near −ρdx0.
Landscape: The generator’s injectivity makes x0 the global optimum, while its non-negativity excludes −y0 from the generator range.These properties resolve the usual sign ambiguity in phase retrieval within the generative model.

3 Main Theoretical Analysis

The analysis establishes deterministic conditions under which the generative-prior objective has favorable geometry, then proves Gaussian weights and measurements satisfy them with high probability. The resulting descent direction is small only near the true solution and its negative multiple.

Descent analysis: The one-sided directional derivative exists everywhere because the generator is piecewise linear, allowing the main result to analyze a nonsmooth objective.The derivative is defined as the unnormalized one-sided directional derivative in a chosen direction.
Gaussian guarantees: Theorem 2 requires m ≥ cdk log(n1n2⋯nd) measurements and layer widths ni ≥ cni−1 log ni−1 under Gaussian generator weights and measurements.Under these conditions, the theorem holds with the stated high-probability bound involving layer widths and m.
Proof strategy: The proof proceeds by establishing deterministic conditions, proving Gaussian ensembles satisfy them, and combining these results through Lemma 1, Proposition 2, and Theorem 3.The theorem’s constants include ρd → 1 as d → ∞, with other dependencies specified by the approximation parameter.
Deterministic conditions: WDC characterizes the Gaussian-like distribution and spatial arrangement of neurons in each layer, while RRCP characterizes measurement behavior on generator outputs.Gaussian Wi and A satisfy WDC and RRCP with high probability.
Deterministic conditions: Theorem 3 shows that WDC for every generator layer and RRCP for A imply the same favorable-geometry conclusion deterministically.Because these conditions are deterministic, the result may extend beyond Gaussian distributions.
Descent analysis: The descent direction concentrates around a continuous vector whose norm is small only near x0 and −ρdx0, establishing the required global geometry.The proof combines uniform concentration from WDC and RRCP with direct analysis of the limiting vector.

4 Numerical Experiments

The experiments compare DPR with sparse phase retrieval methods on synthetic Gaussian signals and MNIST/CelebA image recovery. DPR achieves strong recovery with fewer measurements, while MNIST pixel-level accuracy is limited by the generator’s representational error.

Experimental setup: DPR is evaluated against SPARTA, TWF, and CoPRAM using synthetic Gaussian measurements and pretrained generative models for MNIST and CelebA.The image experiments use gradient descent with Adam, while sparse methods operate on Daubechies-4 wavelet coefficients.
Gaussian signals: DPR nearly matches SPARTA recovering a 10-dimensional latent code when SPARTA recovers a 3-sparse 1000-dimensional signal, and outperforms alternatives at comparable sparsity levels with fewer measurements.The synthetic comparison uses 25 random instances and counts recovery as successful when relative latent-code error is at most 10^-4.
MNIST and CelebA: 200 measurements yield MNIST mean SSIM above 0.9 for DPR, whereas other algorithms require at least 1000 measurements.DPR’s reconstruction error at 200 measurements is comparable to the alternatives at 750 measurements or more.
MNIST and CelebA: DPR’s per-pixel reconstruction error saturates as measurements increase because accuracy is bounded by the generative model’s representational error.The paper notes that semantic measures may better reflect recovery quality in applications such as MRI and molecular structure estimation.
MNIST and CelebA: DPR reconstructions are nearly all semantically correct on MNIST even with 100 measurements, although blank images can have lower pixel error than algorithmic reconstructions.Figure 4 compares reconstructed images at 100 and 300 measurements using a blank-image error reference.
MNIST and CelebA: CelebA experiments reconstruct 10 test images with DPR using 500 measurements, while the alternative methods fail below 5000 measurements.The CelebA images are 64 × 64 RGB images with latent code dimension k = 100.

5 Appendix

The appendix establishes concentration properties for Gaussian generators and measurement matrices, then uses them to characterize the gradient field. The resulting geometry confines near-zero gradient points to neighborhoods of the true code and a negative multiple.

Proof framework: The proof analyzes differentiability and directional derivatives of the empirical risk, including descent behavior near the origin and away from stationary regions.Continuity and piecewise linearity of G and the phaseless map extend gradient-based arguments to nondifferentiable points.
Generator concentration: Gaussian generator weights satisfy the Weight Distribution Condition with high probability when each layer width scales at least as k log k.The stated probability is at least 1 − 8n exp(−γk), with constants depending polynomially on the inverse accuracy parameter.
Gradient concentration: The analysis concentrates the gradient vector around a deterministic vector hx,x0 for all nonzero latent codes under WDC-based bounds.The concentration argument combines bounds on the relevant terms and controls the maximal norm in the near-stationary set by 6d.
Stationary-point geometry: The near-zero set of hx,x0 lies in two neighborhoods centered at x0 and a negative multiple −ρdx0, with ρd approaching 1 as depth increases.The proof separates small-angle and large-angle cases corresponding respectively to x ≈ x0 and x ≈ −ρdx0.
RRCP: The Range Restricted Concentration Property controls measurements of differences between generator outputs uniformly over latent codes.Its proof first establishes concentration on fixed k-dimensional subspaces and then extends the result to the generator range.