PaperlayerView exact revision on arXiv

Source-linked AI summary

The Numerics of Phase Retrieval

Albert Fannjiang, Thomas Strohmer

arXiv:2004.05788v1eess.IVcs.NAmath.NA

TL;DR

Phase retrieval seeks to reconstruct a signal from Fourier magnitudes, a difficult problem for which multiple signals can share the same measurements. This paper reviews recent numerical advances and their theoretical and practical scope, including recovery guarantees and limitations of particular algorithms. Its conclusion calls for systematic numerical analysis to strengthen dialogue between theory and practice.

  • Problem

    Fourier-magnitude measurements can correspond to infinitely many signals beyond trivial associates, making reconstruction ill-posed without further information.

    Source: §2.1 · p. 5

  • Method

    The paper reviews phase-retrieval algorithms from a numerical viewpoint, covering convergence, measurement structures, and data structures.

    Source: §1 · p. 4

  • Results

    For coded diffraction, cited PhaseLift results reduce the measurement count from O(n log^4 n) to O(n log^2 n).

    Source: §6.1 · p. 45

  • Takeaways & Limitations

    The paper calls careful systematic numerical analysis essential to strengthening the bond between theory and practice.

    Source: §9 · p. 74

    Averaged Alternating Reflections can diverge when noisy data make the feasibility problem inconsistent, a case the paper says is prevalent.

    Source: §4.2 · p. 22

Abstract

from arXiv · show

Phase retrieval, i.e., the problem of recovering a function from the squared magnitude of its Fourier transform, arises in many applications such as X-ray crystallography, diffraction imaging, optics, quantum mechanics, and astronomy. This problem has confounded engineers, physicists, and mathematicians for many decades. Recently, phase retrieval has seen a resurgence in research activity, ignited by new imaging modalities and novel mathematical concepts. As our scientific experiments produce larger and larger datasets and we aim for faster and faster throughput, it becomes increasingly important to study the involved numerical algorithms in a systematic and principled manner. Indeed, the last decade has witnessed a surge in the systematic study of computational algorithms for phase retrieval. In this paper we will review these recent advances from a numerical viewpoint.

1. Introduction

Phase retrieval is difficult both because intensity measurements discard phase and because uniqueness results do not ensure practical reconstruction. This paper surveys recent numerical work, emphasizing systematic algorithm study alongside measurement schemes and data structures.

1. Introduction

  • Systematic theoretical and numerical study is presented as necessary for diagnosing failures amid larger datasets and demands for faster throughput.The paper identifies setup mistakes, corrupted measurements, calibration errors, modeling assumptions, and algorithm deficiencies as possible sources of failure.Source: §1 · p. 2
  • Recent activity draws on new imaging capabilities and mathematical ideas, amid applications ranging from X-ray crystallography to optics, microscopy, and quantum physics.The paper situates phase retrieval across multiple imaging and scientific fields.Source: §1 · p. 3
  • Intensity measurements discard phase, leaving infinitely many possible signals; prior structural information, additional phaseless measurements, or both are needed for solvability.Some ambiguities are simple transformations, but others are not.Source: §1 · pp. 3–4
  • Uniqueness conditions do not establish numerical computability or algorithm robustness, and the link between loss and reconstruction error depends on the measurement scheme.Many existing numerical methods also rely on prior information, without proof that they recover the signal.Source: §1 · p. 4
  • The paper reviews recent phase-retrieval advances from an algorithmic viewpoint, giving systematic empirical study, convergence analysis, sampling schemes, and data structures attention.It frames these as relevant to practical performance and diagnosing algorithm failures.Source: §1 · pp. 2, 4

1.1. Overview.

  • The overview covers measurement techniques, uniqueness and noise, nonconvex and convex methods, initialization, blind ptychography, and holographic coded diffraction imaging.It also includes applications in quantum tomography and ways to use signal sparsity.Source: §1.1 · pp. 4–5

2. Phase retrieval and ptychography: basic setup

This section sets up phase retrieval as discrete signal recovery from intensity measurements, noting its ill-posedness and global-phase ambiguity, and outlines measurement strategies, including the connection between ptychographic measurements and short-time Fourier analysis. It then presents 2D lattice-based ptychography with shifted masks, connectivity requirements among measured object parts, and matrix representations relevant to blind ptychography.

2.1. Mathematical formulation.

  • Phase retrieval seeks a signal from squared measurement magnitudes, but is generally ill-posed and exact recovery is only up to global phase.The paper focuses on discrete finite-length signals; Fourier-magnitude data can admit infinitely many solutions beyond phase, reflection, and shift ambiguities.Source: §2.1 · pp. 5–6

2.2. Prior information.

  • Additional prior information or measurements can address ill-posedness; common priors include support, positivity, real-valuedness, atomicity, and sparsity.Twofold Fourier oversampling in each dimension almost always yields uniqueness for finitely supported, real-valued, nonnegative multidimensional signals, but does not establish recovery or algorithmic robustness.Source: §2.1 · p. 6, §2.2 · p. 6, §2.3 · p. 7

2.3. Measurement techniques.

  • Measurement strategies include multiple structured illuminations, coded diffraction, and holography, which uses a reference to recover phase.Multiple views can be produced with masks, gratings, sample rotation, defocusing, or oblique illumination; random illuminations have theoretical support, while holography can be difficult to implement in practice.Source: Multiple structured illuminations · pp. 7–8, Holography · p. 8

2.4. Measurement of coded diffraction patterns.

  • Coded diffraction measures oversampled Fourier intensities of a masked object; the analysis focuses on transparent random phase masks and dimensions d ≥ 2, especially d = 2.With standard oversampling, the diffraction pattern and object autocorrelation are Fourier-transform equivalents; ptychography is a CDI special case that gathers more measurements at the cost of a longer experiment, enabling lensless microscopy with enhanced resolution and robustness.Source: §2.4 · pp. 9–10, §2.5 · p. 10

2.5. Ptychography.

  • Ptychographic measurements are squared Fourier magnitudes of localized, masked object regions scanned with overlap.The measurement at shift t is |F(µ(s)x(s + t))|^2; its specific mathematical structure motivates dedicated reconstruction analysis, including PhaseLift-based approaches [101].Source: §2.5 · pp. 10–11

2.6. Ptychography and time-frequency analysis.

  • Ptychographic measurements correspond to squared magnitudes of the object’s short-time Fourier transform, or a sampled Gabor transform on a time-frequency lattice.Consequently, reconstruction methods for sampled STFT magnitudes are relevant to ptychography.Source: §2.5 · p. 11, §2.6 · p. 12

2.7. 2D Ptychography.

  • In 2D ptychography, a mask smaller than the object shifts across it, producing coded diffraction patterns from overlapping object parts that cover the object.The formulation sets the mask and each restricted object part to zero outside its support and assumes periodic boundary conditions.Source: §2.7 · p. 12
  • A basic 2D scan places shifted masks on a lattice with basis vectors v1 and v2; under periodic boundaries, a raster scan with τ = n/q uses q² positions and wraps edge shifts to the opposite side.The simplest raster scan uses the square-lattice basis v1 = (τ, 0), v2 = (0, τ).Source: §2.7 · pp. 12–13
  • Strong connectivity is a basic requirement: shifted object parts must form a connected graph through overlaps of at least s pixels, with strong connectivity corresponding to s ≫ 1.For full-support objects, the overlap condition is |Mt ∩ Mt′| ≥ s.Source: §2.7 · pp. 12–13
  • The measurement map yields Aν, formed by concatenating Φ diag(νt), and Bx, formed by stacking Φ diag(xt); both have orthogonal columns and are relevant to blind ptychography.Aν represents measurements for a given mask, while Bx represents them for a given object.Source: §2.7 · p. 13

3. Uniqueness, ambiguities, noise

This section reviews uniqueness and feasibility, ambiguities in single-pattern recovery, and noise models. It also connects measurement geometry to local properties of loss functions.

3.1. Uniqueness and ambiguities with coded diffraction patterns.

  • With independent continuous random mask phases, coded-diffraction uniqueness up to global phase holds with high probability under a phase-range condition for one pattern, and with probability one for two; ptychographic uniqueness follows under connectivity.The one-pattern probability bound improves exponentially with object sparsity.Source: §3.1 · pp. 14–15

3.2. Ambiguities with one diffraction pattern.

  • For one diffraction pattern, ambiguities can include translation, conjugate inversion, and modulation; a real-valued prior excludes them almost surely with a random mask, but a uniform mask permits them.Conjugate inversion is especially prevalent and cannot be eliminated by a tight support constraint; a uniform mask may also permit other ambiguities.Source: §3.2 · pp. 15–16
  • For integer Fresnel parameter f, a twin-like ambiguity can occur; experiments also show relative error and residual spikes at integer f, with spill-over worsening as q increases.The experiment used a 50% overlap raster scan and 200 AAR iterations followed by 100 AP iterations.Source: Twin-like ambiguity with a Fresnel mask · pp. 16–17

3.3. Phase retrieval as feasibility.

  • The feasibility view works in the transform-domain range of A: uniqueness up to phase corresponds geometrically to the intersection X ∩ Y being a circle.The problem is formulated as finding a point in the intersection of the two constraint sets.Source: §3.3 · pp. 17–18

3.4. Noise models and log-likelihood functions.

  • With known noise statistics, maximum likelihood motivates the loss; complex Gaussian interference yields an amplitude-based loss at low noise, while thermal Gaussian noise has a smooth loss.For the interference model, squaring the observation gives additive Gaussian noise with variance proportional to |Ax∗|².Source: §3.4 · p. 18, Complex Gaussian noise · p. 19, Thermal noise · p. 19
  • The amplitude-based Gaussian loss (17) generally outperforms the intensity-based loss (21), while the Poisson loss (14) has a divergent derivative when u(i)=0 but b(i)≠0.The divergence can be softened by introducing a regularization parameter.Source: Poisson noise · p. 18, Thermal noise · p. 19

3.5. Spectral gap and local convexity.

  • With probability one, the relevant spectral quantity is below 1; the Hessian of loss (17) at Ax∗ is positive semidefinite, with its zero-eigenvalue eigenspace spanned by ix∗.The Hessian statement assumes Ax∗ is nonvanishing almost surely.Source: §3.5 · p. 20

4. Nonconvex optimization

The section reviews alternating-projection and reflection methods for nonconvex phase retrieval, relating their iteration behavior to feasibility and loss minimization. It describes when these methods converge, how their fixed points can differ from true solutions, and where convergence can stall.

4.1. Alternating Projections (AP).

  • AP is a projection-based approach whose fixed points can include non-solutions, which appear as local minima of the loss and are associated with numerical stagnation.The existence of such fixed points is not proved in the cited discussion.Source: §4.1 · pp. 20–21
  • AP can be written as a constant-step-size sub-gradient descent for the loss, while projecting onto the data set makes it noise-agnostic and the loss descent makes it noise-aware.The stated step size is 1; local geometric convergence to x* is also reported.Source: §4.1 · p. 21
  • Every limit point of the AP sequence is a fixed point, and a norm criterion distinguishes phase-retrieval solutions from other coexisting fixed points.Under the stated conditions, the sequence is bounded for any starting point.Source: §4.1 · p. 21

4.2. Averaged Alternating Reflections (AAR).

  • For AAR, consistent convex feasibility yields convergence to a generalized solution, but inconsistent feasibility makes iterates diverge, a drawback common with noisy data.The cited discussion attributes the prevalence of inconsistency with noisy data to the data dimension being higher than the object dimension.Source: §4.2 · p. 22
  • AAR fixed points can be generalized solutions with the correct Fourier phase, yet degenerate boundary points can slow convergence and global behavior from random starts is described as sublinear.Applying the projection onto X at the right time can jump-start geometric convergence.Source: §4.2 · p. 23

4.3. Douglas-Rachford Splitting (DRS).

The section presents Douglas–Rachford splitting as a modification of AAR using proximal maps. It notes that alternative proxy functions can produce variants with potentially more desirable properties.

4.3. Douglas-Rachford Splitting (DRS).

  • Douglas–Rachford splitting modifies AAR by applying a three-step procedure to proximal maps.Proximal maps generalize projections.Source: §4.3 · pp. 23–24
  • The projections onto X and Y are proximal maps for their respective indicator functions.Source: §4.3 · p. 24
  • Choosing proxy functions other than the indicator functions may yield DRS methods with more desirable properties than AAR.Source: §4.3 · p. 24

4.4. Convergence rate.

The section relates local convergence rates to the second-largest singular value, contrasts Fourier- and object-domain formulations, and describes Wirtinger Flow's initialization-plus-gradient approach and theoretical guarantees.

4.4. Convergence rate.

  • AAR and AP have local geometric convergence rates λ2 and λ2^2, respectively, where λ2 is the second-largest singular value of B.The section notes that AP's rate is faster than DR's because λ2^2 < λ2, and suggests using AAR to initialize AP to combine their strengths.Source: §4.4 · p. 24

4.5. Fourier versus object domain formulation.

  • The object-domain version of AAR significantly underperforms Fourier-domain AAR, while zero-padding and explicitly enforcing the added support constraint are described as a way to rectify the issue.The difference is tied to the rectangular measurement matrix having more rows than columns.Source: §4.5 · p. 25

4.6. Wirtinger Flow.

  • Wirtinger Flow's theoretical framework gives guarantees in terms of measurement requirements, convergence rate, and robustness; modifications can seek global convergence with random initialization at the cost of more measurements.Source: §4.6 · pp. 25, 27
  • Wirtinger Flow combines a spectral initialization with iterative gradient descent and is presented as computationally efficient with rigorous recovery guarantees.The cited theorem assumes Gaussian measurement vectors and N ≥ c0 n log n measurements, along with a bounded constant step size.Source: §4.6 · pp. 25–26

4.7. Alternating Direction Method of Multipliers (ADMM).

The section introduces ADMM for a joint optimization problem with a linear constraint, specifying loss and constraint functions for phase retrieval. It also situates ADMM relative to Douglas–Rachford splitting.

4.7. Alternating Direction Method of Multipliers (ADMM).

  • For phase retrieval, DRS and ADMM are described as essentially equivalent, so the presentation focuses mostly on ADMM.Source: §4.7 · p. 27
  • ADMM is presented as a method for the joint optimization problem with a linear constraint, using an augmented Lagrangian and multiplier updates by gradient ascent.Source: §4.7 · p. 27
  • The ADMM formulation uses the indicator function of X as K and either the Poisson or Gaussian loss as L.Source: §4.8 · p. 27

4.8. Noise-aware ADMM.

This section formulates noise-aware DRS updates through proximal maps for Gaussian and Poisson loss functions. For Gaussian loss, the proximal relaxation has properties that are false or unproven for AAR.

4.8. Noise-aware ADMM.

  • The Gaussian-DRS update uses the proximal map in place of the update in (38)–(40).The update is specified in the passage as w_l = prox_{L/ρ}(2v_l − u_l), followed by u_{l+1} = u_l + w_l − v_l.Source: §4.8 · pp. 27–28
  • Gaussian loss yields an exact proximal map, and its relaxed update is an averaged projection with relaxation parameter ρ.The resulting iteration is identified as the Gaussian-DRS map.Source: §4.8 · p. 28
  • The Poisson DRS map has a more complicated form than the Gaussian case.The passage defines b² componentwise as b²(j) = (b(j))².Source: §4.8 · p. 29
  • With the proximal relaxation in (54), the authors ascertain desirable properties that are false or unproven for AAR.The maps Γ(u) and Π(u) are continuous except where RXu vanishes but b does not.Source: §4.9 · p. 29, §4.8 · p. 29

4.9. Fixed points.

The fixed-point analysis relates Gaussian-DRS fixed points and local convergence to regular solutions, while also identifying behavior in inconsistent problems. It further characterizes the parameter associated with the optimal local convergence rate.

4.9. Fixed points.

  • For ρ > 0, Gaussian-DRS iterates are bounded by ∥b∥ min{ρ, 1}; at ρ = 1, every fixed point has norm ∥b∥.The bound is presented as avoiding the divergence behavior of AAR when the feasibility problem is inconsistent and has no generalized or regular solution.Source: §4.9 · p. 29
  • For ρ ≥ 1, the stated conditions on a fixed point and its Jacobian imply that it is a regular solution.The passage identifies all attracting points under those conditions as regular solutions.Source: §4.9 · p. 29
  • In inconsistent problems, Gaussian-DRS fixed points are locally repelling in some directions, so convergence is impossible.The passage notes that noisy measurements can prohibit a regular solution; Gaussian-DRS nevertheless performs well in noisy blind ptychography, with an error amplification factor of about 1/2.Source: §4.9 · p. 30
  • For ρ ≥ 0, nonvanishing regular solutions are attracting fixed points of Gaussian-DRS.The cited theorem states that the Jacobian is nonexpansive at such a solution.Source: §4.9 · p. 30
  • The second-largest singular value of the Gaussian-DRS Jacobian is minimized at ρ*, identifying the parameter for the optimal convergence rate.It decreases up to ρ* and increases after it; the leading singular value is 1 and the second-largest is strictly less than 1.Source: §4.9 · p. 30

4.10. Perturbation analysis for Poisson-DRS.

The section derives a perturbed DRS for small positive ρ in the Poisson case and notes that two limiting procedures yield different constants. It also introduces RAAR as another noise-agnostic method.

4.10. Perturbation analysis for Poisson-DRS.

  • For small positive ρ, the Poisson-DRS is approximated by retaining terms through O(ρ).The passage presents the resulting perturbed DRS expression.Source: §4.10 · p. 30
  • The small-ρ limit and the Poisson-to-Gaussian limit do not commute, producing a different constant from Theorem 4.6.The authors describe the Poisson-DRS analysis as a perturbative derivation of an analogous result for small positive ρ.Source: §4.10 · pp. 30–31
  • RAAR is introduced as another noise-agnostic method alongside AAR.Source: §4.11 · p. 31

4.11. Noise-agnostic method.

The section presents RAAR as a noise-agnostic method derived through an ADMM formulation and describes its relation to AAR and its bounded iterates. It also specifies a reconstruction choice for inconsistent noisy phase retrieval.

4.11. Noise-agnostic method.

  • RAAR’s hard constraint is oblivious to measurement noise, while K relaxes the object-domain constraint.Source: §4.11 · p. 31
  • For an inconsistent noisy problem, the minimizer is a generalized solution with the least inconsistent component, and PXz* can be used for reconstruction.For a consistent noisy problem, the minimum is zero and the minimizer is a regular solution for the noisy data.Source: §4.11 · p. 31
  • The ADMM formulation yields the RAAR map, which becomes AAR when β = 1.The passage says the map follows by substitution and algebra.Source: §4.11 · p. 32
  • RAAR iterates satisfy ∥u_{k+1}∥ ≤ β∥u_k∥ + ∥b∥, giving an explicit bound in terms of β.The passage states that local geometric convergence of RAAR has been proved.Source: §4.11 · p. 33

4.12. Optimal parameter.

The section compares Gaussian-DRS with AAR, APR, and RAAR, finding that its performance depends on the relaxation parameter. APR outperforms AAR but underperforms RAAR, while Gaussian-DRS can closely match or outperform RAAR at lower parameter values.

4.12. Optimal parameter.

  • The comparison uses AAR, RAAR, and Gaussian-DRS with ρ = 1 as baselines on a 256-by-256 Cameraman+ i Barbara test image and two coded diffraction patterns.The patterns are a plane wave and a random-phase illumination; reconstruction error is measured modulo a constant phase factor.Source: §4.12 · pp. 33, 35
  • For ρ ≥ 1, Gaussian-DRS with ρ = 1 produces the best convergence rate among ρ ≥ 1, and the regular solutions are attracting for ρ ≥ 0.For ρ ≥ 1, no fixed points other than regular solutions are locally attracting; the simplicity of equation (74) motivates the name Averaged Projection Reflection (APR).Source: §4.12 · pp. 33–34
  • The experiment sets β = 0.9 for RAAR, corresponding to ρ = 0.333 under the stated parameter relation.The cited guidance places optimal β usually between 0.8 and 0.9, corresponding to ρ between 0.125 and 0.333.Source: §4.12 · p. 35
  • In the semi-log error plots, all methods except AAR show straight-line behavior indicating global geometric convergence; AAR's behavior from random initialization is less clear.AAR has been shown to converge geometrically near the true object after applying A+, but at a power-law rate from random initialization.Source: §4.12 · p. 35
  • At ρ = 0.3, Gaussian-DRS significantly outperforms RAAR; at ρ = 0.5 or 0.1, it closely matches RAAR, while APR outperforms AAR but underperforms RAAR.The tested Gaussian-DRS values were ρ = 1.1, 0.5, 0.3, and 0.1; its oscillation at ρ = 0.1 is attributed to a dominant complex eigenvalue of J.Source: §4.12 · p. 35

5. Initialization strategies

The section reviews spectral, null-vector, and optimally preprocessed initializers, alongside random initialization, and compares their theoretical properties and empirical performance. In the experiments, the optimal spectral initializer is strongest when measurements are few, while random initialization can perform comparably at lower computational cost when measurements are more plentiful.

5.1. Spectral initialization.

  • Spectral initialization uses the leading eigenvector of a positive semidefinite Hermitian matrix built from measurements, computable by the power method.Under Gaussian measurements, the infinite-sample matrix has a leading eigenvector proportional to the true signal, so this initializer recovers it up to global phase; finite-sample accuracy is tied to concentration and a Wirtinger Flow guarantee.Source: §5.1 · pp. 35–36

5.2. Null initialization.

  • Null initialization uses measurements below a threshold to form a weak-signal set and estimates the object from the ground state of its sub-row matrix.The geometric mean threshold rule attains the stated asymptotic minimum error bound; the null vector is described as robust to noise when the weak-signal set can be reduced to avoid corrupted indices near the threshold.Source: §5.2 · pp. 36–37

5.3. Optimal pre-processing.

  • For the sphere and complex-Gaussian measurement model, no algorithm gives non-trivial estimates when δ < 1, whereas a spectral algorithm gives weak recovery for δ > 1 at sufficiently low noise.The optimal preprocessor permits negative diagonal values in T and is reported to yield the smallest possible threshold δu for that signal model; its large negative part for small measurements may slow power-method convergence.Source: §5.3 · p. 38

5.4. Random initialization.

  • Random initialization is a low-cost alternative, and Gaussian-measurement theory establishes convergence to the true solution at a favorable rate when N ≳ n log^13 N.The authors call this theoretical condition somewhat less compelling because of its large logarithmic exponent, while suggesting the exponent may reflect proof challenges and noting that simulations support this view.Source: §5.4 · pp. 38–39

5.5. Comparison of initializations.

  • For 2 OCDPs, xnull has lower relative error than xop at NSR 0%, 10%, and 20%: 0.6531, 0.6943, and 0.8146 versus 1.3636, 1.3952, and 1.3889.The optimal preprocessing output is described as essentially random at all three noise levels.Source: §5.5 · p. 40
  • For 4 CDPs, xop has lower relative error than xnull at NSR 0%, 10%, and 20%: 0.6269, 0.6437, and 0.6888 versus 0.7374, 0.7761, and 0.8991.The authors attribute the contrast to sampling: oversampled CDPs favor the null vector, whereas standard CDPs favor optimal preprocessing, which is optimized for independent measurements and fares poorly with highly correlated oversampled data.Source: §5.5 · p. 40
  • The initializer comparison evaluates standard, truncated, and optimal spectral, null, and random starts using iteration count, runtime, and successful recovery.Wirtinger Flow is run across 3–12 diffraction illuminations, with success defined as relative ℓ2 error below 0.1; each result averages 10,000 runs per illumination count.Source: §5.5 · pp. 40–41
  • With only three illuminations, the optimal spectral initializer significantly outperforms the alternatives; with a moderate number, random initialization performs as well as the others at lower computational cost.As illuminations increase, the performance difference becomes less pronounced; the authors conclude that using random initialization is not cost-free when fewer illuminations would otherwise suffice.Source: §5.5 · pp. 41–42

6. Convex optimization

This section surveys convex optimization approaches to phase retrieval, including PhaseLift’s lifted trace-minimization and methods without lifting, as well as convex and other numerical methods for low-rank quantum-state and sparse-signal settings. It also covers generative-model extensions and recovery guarantees and limitations, which vary across methods.

6.1. PhaseLift: Phase retrieval via matrix completion.

  • PhaseLift replaces NP-hard rank minimization with trace minimization over positive semidefinite matrices; random sphere measurements yield exact recovery with high probability for N ≥ c0 n log n.The theorem assumes independently and uniformly sampled measurement vectors and a sufficiently large constant c0.Source: §6.1 · pp. 43–44
  • For coded diffraction measurements, PhaseLift’s measurement requirement improved from O(n log^4 n) to O(n log^2 n).The first result uses specifically designed random masks; the improved bound is attributed to.Source: §6.1 · p. 45

6.2. Convex phase retrieval without lifting.

  • PhaseMax avoids lifting by maximizing alignment with a sufficiently close anchor under relaxed measurement constraints; for Gaussian measurements, N ≥ cn ensures exact recovery with high probability when ∥u − x∥2 ≤ 0.6∥x∥2.PhaseLamp iteratively applies PhaseMax through successive linearization and maximization over a polytope.Source: §6.2 · pp. 47–48
  • Another no-lifting approach uses a sequence of convex problems affine in x*, but provides no theoretical conditions guaranteeing recovery of the true signal.Source: §6.2 · p. 48
  • PhaseLift and PhaseLamp reconstructions are visually indistinguishable from the original, while PhaseMax is less accurate in this noiseless, three-illumination example.The comparison uses three coded diffraction illuminations.Source: §6.2 · pp. 48–49, Figure 15 · p. 49
  • Convex methods can recover signals from few phaseless observations, but have not found practical use; PhaseLift is computationally less efficient than nonconvex methods despite fast implementations.PhaseLift also spurred systematic study of numerical algorithms and initialization design for nonconvex solvers.Source: §6.2 · p. 49

6.3. Low-rank phase retrieval problems.

  • Low-rank phase retrieval generalizes the problem to recovering an unknown rank-r positive semidefinite matrix from linear functionals, with the factorization M = XX*.Source: §6.3 · p. 50
  • Low-rank quantum tomography must address measurement design, experimental realizability, noise, and approximate rank; the Zauner conjecture can be expressed as a more challenging phase retrieval problem.A simple alternating-projection method works efficiently for n<100, but appears to get stuck in local minima for larger n.Source: §6.3 · pp. 50–51

6.4. Phase retrieval, sparsity and beyond.

  • For Gaussian measurements, N=O(s2 log n) measurements suffice for the sparse-recovery SDP, but direct ℓ1-penalization cannot attain the hoped-for O(s log n) complexity.The SDP uses the entrywise ℓ1 norm as a convex surrogate for sparsity and the trace as a surrogate for rank.Source: §6.4 · p. 53
  • Sparse Wirtinger Flow and truncated amplitude flow require at least O(s2 log n) samples, while thresholded Wirtinger Flow achieves optimal convergence rates under sub-exponential noise.Iterative sparsity enforcement can use hard or soft thresholding, applied in the basis where the signal is sparse.Source: §6.4 · p. 53
  • A two-stage method for one-dimensional Fourier phase retrieval experimentally recovers s-sparse signals from O(s2) measurements, although its theoretical guarantees require more measurements.It first identifies the support combinatorially, then recovers signal values on that support using a convex algorithm.Source: §6.4 · pp. 53–54
  • A generative-model approach has favorable global geometry for gradient methods under technical conditions with N=O(sd2 log n), while deep-learning methods often lack reconstruction theory and require retraining after input-resolution changes.The section suggests using deep learning as a data-driven regularizer while retaining the physical inverse-problem model [121].Source: §6.4 · p. 54
  • AMP methods are scalable and often work well in practice despite generally heuristic or absent guarantees, whereas randomized Kaczmarz has exponential convergence comparable to the linear setting [105].The section notes that AMP guarantees are at best asymptotic and that most phase-retrieval AMP methods have none.Source: §6.4 · p. 54

7. Blind ptychography

This section examines uniqueness in blind ptychography in light of object–mask and scan-induced ambiguities, rigidity conditions, and scan design. It also covers iterative reconstruction algorithms and extensions, including how scan overlap and mask initialization affect convergence and how Gaussian and Poisson variants compare in noiseless and noisy experiments.

7. Blind ptychography

  • Blind ptychography has affine-phase and scaling ambiguities; the affine-phase transformation preserves the data regardless of the shift set or mask type.When the mask is exactly known, neither ambiguity occurs.Source: §7 · p. 55
  • Local rigidity requires mask phase constraint and an anchored, s-connected object-part family; under these conditions it holds with probability exponentially close to 1 in s [57].Anchors have support touching all four sides of a measurement block, and both anchoring and MPC are nearly necessary for local rigidity.Source: Local rigidity · pp. 55–56
  • Extremely sparse objects can violate the anchoring assumption, making the local-rigidity conditions challenging to satisfy.An object part is an anchor when its support touches four sides of its measurement block.Source: Local rigidity · p. 56
  • For cyclic shifts, block-phase increments form an arithmetic progression in multiples of 2π/s; full raster scans have an affine block-phase profile with increments in multiples of 2π/q.These blockwise ambiguities differ from the pixel-varying affine phase ambiguity.Source: Raster scan ambiguities · p. 57
  • Raster grid pathology arises when ambiguity in initial sub-blocks propagates into periodic artifacts across other sub-blocks.The initial ambiguity can have the maximum degrees of freedom over the respective sub-blocks.Source: Raster scan ambiguities · p. 58
  • Ptychographically complete schemes achieve global rigidity under MPC; a perturbed scan is an example and needs overlap slightly greater than 50%.The section identifies 50% overlap as roughly the minimum required for uniqueness among the specified perturbed raster scans.Source: Global rigidity · p. 59, Minimum overlap ratio · p. 60
  • Below 50% overlap, a perturbed scan can retain nontrivial ambiguity, with dimension at least (2τ1 − m)^2 or (2n − 2τ1 − m)^2, depending on whether 2τ1 < n or 2τ1 > n.The ambiguity is constructed by jointly modifying the object and mask while preserving their diffraction patterns.Source: Minimum overlap ratio · pp. 60–61

7.1. Algorithms for blind ptychography.

  • Blind ptychography is doubly non-convex, so initialization is crucial; the algorithm section initializes the mask from MPC(δ), with independent uniform phases in (−πδ, πδ).The weakest uniqueness condition is δ = 0.5, equivalent to ℜ(ν0 ⊙ µ0) > 0.Source: Initial mask estimate · pp. 61–62
  • eGaussian-DRS converges significantly faster than eRAAR; for eGaussian-DRS, greater scan overlap and lower initial mask phase uncertainty speed convergence, with straight semi-log traces indicating geometric convergence.The comparison used ρ = 1/3 for eGaussian-DRS and β = 0.8 for eRAAR.Source: Figure 20 · p. 64, Extended Gaussian-DRS · p. 64, Figure 21 · p. 66
  • eRAAR extends RAAR to blind ptychography, reduces to RAAR when the mask is known, and uses a non-standard loss with a non-separable term.Source: Extended RAAR · pp. 65–66

7.2. Further extensions of blind ptychography algorithms.

  • The one-loop method alternates object and mask updates, whereas the two-loop method adds inner object and mask loops and is an example of alternating minimization; its Gaussian- and Poisson-DRS versions are called DRSAM.Source: One-loop version · p. 67, Two-loop version · p. 67, Two-loop experiments · p. 68
  • Noiseless convergence rates were 0.8236 (rank-one Poisson), 0.8258 (rank-one Gaussian), 0.7205 (full-rank Poisson), and 0.7373 (full-rank Gaussian); full-rank was faster, and Poisson slightly beat Gaussian.DRSAM also converged geometrically with ρ = 1, overlap slightly above 50%, and initial mask phase uncertainty δ = 1/2, although ρ was far from its near-0.3 optimal value.Source: Figure 22 · p. 68, Two-loop experiments · p. 68
  • At NSR ≥35%, Gaussian-DRS outperforms Poisson-DRS, especially as Poisson reconstruction error becomes unstable; fast convergence with the Poisson log-likelihood may introduce noisy artifacts and reduce reconstruction quality.The experiments limited DRSAM to 100 epochs, and the relative error usually stabilized after 30 epochs.Source: Two-loop experiments · pp. 68–69, Figure 22 · p. 68

8. Holographic coherent diffraction imaging

Holographic CDI adds a known reference to turn phase retrieval into linear deconvolution; the review discusses reference-dependent errors and reports better recovery than HIO.

8. Holographic coherent diffraction imaging

  • Adding a reference makes the cross-correlation term available as a linear recovery problem, unlike the quadratic autocorrelation problem.With the reference signal r, the enlarged specimen is [x*, r].Source: §8 · p. 70
  • The deconvolution matrix is invertible exactly when the reference’s bottom-right entry is nonzero, the separation condition that prevents aliasing.Source: §8 · p. 71
  • References differ in their advantages and drawbacks under noise, and a pinhole reference may be difficult to realize at the required digital resolution.Source: §8 · pp. 71–72
  • The mimivirus experiment uses a 64 × 64 image, a 1024 × 1024 oversampled transform, and Poisson shot noise; oversampling requires known-transmission support around the specimen.For biological imaging, the passage gives levitation or a homogeneous transparent film as examples of suitable surroundings.Source: §8 · p. 72
  • A dual reference achieves smaller recovery error than leading single-reference schemes, while single-reference performance depends on the image’s spectral decay.Source: §8 · p. 72
  • Referenced deconvolution clearly outperforms HIO, with or without enforcing the known reference, and its expected and empirical recovery errors closely match.The figure caption says errors should be rescaled by 10^-4.Source: §8 · p. 72, Figure 24 · p. 73

9. Conclusion and outlook

The review surveys numerical advances in phase retrieval and their implications for algorithms and measurement protocols. It closes by identifying difficult applications and calling for closer theory–practice exchange supported by systematic numerical analysis.

9. Conclusion and outlook

  • Advances in convex and non-convex optimization have improved understanding of the benefits and limitations of phase-retrieval algorithms, and informed new measurement protocols such as random illuminations.Source: §9 · p. 74
  • Blind ptychography, single-molecule protein imaging, and single-shot non-crystallographic X-ray imaging remain challenging; the last also requires 3D reconstruction with unknown rotation angles.Source: §9 · p. 74
  • The review urges testing whether assumptions that differ from current practice are unrealistic or could inspire implementable ideas.Source: §9 · p. 74
  • The authors call for closer dialogue between practitioners and theorists, with careful systematic numerical analysis strengthening their feedback loop.Source: §9 · p. 74

Related papers

Loading 2004.05788v1…