Source-linked AI summary
Phase Retrieval via Matrix Completion
Emmanuel J. Candes, Yonina Eldar, Thomas Strohmer, Vlad Voroninski
TL;DR
Phase retrieval asks how to recover a signal from intensity or Fourier-magnitude measurements despite non-uniqueness and lost phase. The paper uses structured illuminations with lifted, convex matrix recovery and noise-aware optimization. Its theory establishes exact recovery from three patterns under stated primality conditions, while experiments show successful recovery with a few patterns and Gaussian masks.
Problem
Phase retrieval must recover signals from magnitude measurements that can correspond to infinitely many signals, while existing methods may lack recovery guarantees or stability under noise.
Method
The paper combines multiple coded illuminations with PhaseLift, which lifts quadratic measurements to a rank-one matrix problem and applies convex trace-norm minimization with noise-aware modeling.
Results
3n real measurements uniquely recover x up to global phase under the one-dimensional theorem’s stated primality and nonvanishing-DFT conditions when the convex or reweighted program returns rank one.
Takeaways & Limitations
Three structured diffraction patterns can suffice for exact phase recovery under the paper’s multidimensional primality conditions, while experiments support recovery from only a few illuminations.
Takeaways & Limitations
The reweighting heuristic may fail to find the global minimum because its objective functional is concave.
Abstract
from arXiv · showhide
This paper develops a novel framework for phase retrieval, a problem which arises in X-ray crystallography, diffraction imaging, astronomical imaging and many other applications. Our approach combines multiple structured illuminations together with ideas from convex programming to recover the phase from intensity measurements, typically from the modulus of the diffracted wave. We demonstrate empirically that any complex-valued object can be recovered from the knowledge of the magnitude of just a few diffracted patterns by solving a simple convex optimization problem inspired by the recent literature on matrix completion. More importantly, we also demonstrate that our noise-aware algorithms are stable in the sense that the reconstruction degrades gracefully as the signal-to-noise ratio decreases. Finally, we introduce some theory showing that one can design very simple structured illumination patterns such that three diffracted figures uniquely determine the phase of the object we wish to recover.
1 Introduction
Phase retrieval seeks to recover signals from Fourier-magnitude measurements, but these data are generally non-unique and existing methods can be unstable or require restrictive assumptions. The paper instead combines unconstrained signal recovery with lifting, convex optimization, structured illuminations, and noise-aware modeling.
- 1.1 The phase retrieval problem: Phase retrieval recovers a signal from the magnitude of its Fourier transform, where detectors often lose phase information that encodes structural content.The problem occurs in applications including X-ray crystallography, diffraction imaging, optics, astronomical imaging, and microscopy.
- 1.1 The phase retrieval problem: Fourier-magnitude data admit trivial ambiguities and, in general, infinitely many additional signals with the same measurements.Global phase, reversal, and shifts are acceptable ambiguities, but nontrivial non-uniqueness remains.
- 1.2 Main approaches to phase retrieval: Existing approaches often rely on positivity, support, atomicity, real-valuedness, or oversampling, while uniqueness results do not guarantee recovery, robustness, or stability from noisy data.Alternating-projection methods also require careful constraints and parameter selection, and their convergence is not generally established.
- 1.3 PhaseLift – a novel methodology: The paper removes signal constraints by lifting quadratic measurements to affine constraints on a rank-one matrix and relaxing rank minimization to a convex matrix-completion program called PhaseLift.The recovered rank-one matrix can be factorized as xx∗, connecting phase retrieval to low-rank matrix recovery.
- 1.3 PhaseLift – a novel methodology: Multiple coded illuminations and trace-norm minimization provide a systematic framework for handling noisy measurements and statistical noise models.The authors describe the framework as an elaborate regularized maximum-likelihood method and emphasize structured illuminations combined with convex programming.
2 Methodology
The methodology combines multiple structured illuminations with PhaseLift, which lifts quadratic intensity measurements to affine constraints on a rank-one positive semidefinite matrix. Convex trace-based and noise-aware likelihood formulations provide tractable recovery programs, while reweighting offers a closer rank surrogate but is only heuristic.
- Structured illumination: Multiple structured illuminations generate different diffraction views through masks, gratings, ptychography, or oblique beams, with fewer patterns preferred for stable recovery.The paper discusses phase masks, optical gratings, scanned finite illuminations, and user-specified oblique angles.
- Lifting: PhaseLift lifts quadratic measurements into linear constraints on X = xx∗, recovering the signal by factorizing a rank-one positive semidefinite matrix.The lifted formulation maps X through linear trace measurements and imposes positive semidefiniteness and rank one.
- Convex recovery: Trace-norm minimization replaces NP-hard rank minimization with a convex semidefinite program, although formal equivalence conditions are generally unavailable for diffraction matrices.The trace formulation nevertheless shows strong empirical performance in the paper’s experiments.
- Noise modeling: Noise-aware PhaseLift minimizes a negative log-likelihood plus λ Tr(X), yielding a regularized maximum-likelihood formulation that is convex for log-concave likelihoods.The framework includes Poisson and Gaussian noise models and trades off fit quality against model complexity.
- Reweighting: The log-det objective more closely approximates rank, and under the stated sensing assumptions its unique minimizer matches the phase-retrieval solution up to global phase.The theorem states this conclusion for all ε > 0 when A is one to one and I lies in the sensing-matrix span.
- Reweighting: Reweighting is tractable but heuristic because its concave objective means the procedure cannot always be expected to find the global minimum.This limits the guarantee of the reweighted approach despite its usefulness for phase retrieval.
3 Theory
The theory studies when a small number of structured diffraction measurements uniquely determine phase. It gives arithmetic conditions for exact uniqueness in one and two dimensions, while identifying Fourier zeros and incomplete frequency cycles as obstructions.
- Scope: The theory asks when multiple diffracted images imply uniqueness and when the convex heuristic succeeds in recovering that unique solution.The paper provides partial answers focused on designing simple diffraction patterns with uniqueness.
- One-dimensional recovery: 3n real measurements recover a 1D signal up to global phase exactly when the modulation shift s is prime with n and the DFT does not vanish.Under primality, a rank-1 solution returned by trace minimization or iterative reweighting is exact.
- Two-dimensional recovery: The 2D measurement construction recovers phase differences along the cyclic subgroup generated by (s1, s2), whose full order requires the stated coprimality conditions.The resulting measurements use the unmodulated pattern and two modulated patterns involving x + Dsx and x − iDsx.
- Two-dimensional recovery: In 2D, 3n1n2 measurements give recovery up to global phase when s1 is prime with n1, s2 is prime with n2, n1 is prime with n2, and the DFT does not vanish.Under these conditions, a rank-1 solution from trace minimization or iterative reweighting is exact.
- Two-dimensional recovery: Using horizontal and vertical modulations instead guarantees recovery with 5n1n2 measurements for all dimensions when each shift is prime with its corresponding dimension.Alternatively, zero-padding one dimension can enforce the required primality relationship with slight Fourier oversampling.
- One-dimensional recovery: Recovery fails when Fourier zeros disconnect the phase-difference relations, leaving independent frequency groups whose relative phase is undetermined.A smaller cyclic subgroup also ends before all phases are recovered, preventing further phase determination without extra assumptions.
- General modulation design: More generally, 2D recovery with (2K + 1)n1n2 measurements is possible when the modulation shifts generate Z/n1Z × Z/n2Z and the Fourier transform has no nonzero components.This generalizes the single-shift construction through group generators.
4 Numerical Experiments
This section introduces numerical simulations to illustrate and study the effectiveness of PhaseLift.
- Numerical simulations illustrate and study the effectiveness of PhaseLift.
4.1 Numerical solvers
The numerical solvers formulate phase retrieval as a convex optimization problem and use accelerated first-order methods. For large signals, a low-rank factorization proxy reduces memory and computation, but its convergence is not guaranteed.
- Implementation: The algorithms were implemented in Matlab using TFOCS and modified TFOCS templates for convex optimization problems.
- Convex optimization: The objective minimizes a smooth negative log-likelihood plus a trace penalty over the positive semidefinite cone.Projected gradient methods update an iterate using a gradient step followed by projection onto the cone.
- Accelerated methods: TFOCS implements accelerated first-order methods that evaluate gradients at an auxiliary sequence and typically require fewer iterations than projected gradient methods.The per-iteration computational work remains comparable to projected gradient methods.
- Large-scale implementation: For large images, the computational approach maintains a low-rank factorization of the optimization variable instead of storing the full N × N matrix.It replaces the expensive semidefinite-cone projection with a proxy that retains only the k largest eigenvalues.
- Large-scale implementation: Using k between 10 and 20 makes the low-rank approximation efficient, but convergence is no longer guaranteed.Each iteration only requires the top eigenvectors of a low-rank matrix.
4.2 Setup
The paper evaluates reconstruction error relative to the unavoidable global-phase ambiguity and extracts a rank-one signal from the optimization solution when necessary.
- Error metric: Relative MSE compares the reconstruction with the solution space after minimizing over the unknown global phase.This avoids measuring distance to one arbitrary representative of the phase-equivalent solutions.
- Error metric: The paper defines SNR analogously from relative MSE using SNR = log10(rel. MSE).
- Rank-one extraction: Because the algorithm may return an optimal matrix that is not rank one, the reconstruction is obtained from an eigenvector associated with its largest eigenvalue.The extracted vector is scaled so its ℓ2 norm matches that of the true signal, which is available from the diffraction pattern via Parseval’s theorem.
4.3 1-D simulations
The one-dimensional simulations test PhaseLift on noiseless and noisy signals, using structured illuminations and relative MSE to assess recovery. The experiments show strong noiseless reconstruction, graceful noise degradation, and persistent ambiguity under oversampling alone.
- 4.3.1 Noisefree measurements: Two length-128 signals—a sinusoidal optics-like signal and a complex Gaussian signal—were recovered from noiseless measurements.The experiments were designed to test two substantially different signal types.
- 4.3.1 Noisefree measurements: Four random binary masks produced 512 intensity measurements for the noiseless experiments.The recovery used a trace-regularized positive semidefinite objective with a small λ and reweighting.
- 4.3.1 Noisefree measurements: 87.3dB and 90.5dB SNR were obtained for the two noiseless test signals, while three Gaussian-mask illuminations achieved similar performance.The Gaussian-mask result used one fewer illumination than the binary-mask experiment.
- 4.3.2 Noisy measurements: The noisy experiments used eight binary-mask illuminations and Poisson noise across five SNR levels ranging from about 16dB to about 52dB.
- 4.3.2 Noisy measurements: The error curves showed linear SNR–MSE behavior and graceful degradation as SNR decreased; about 5dB separated four- and eight-measurement curves, corresponding to almost twofold error reduction.
- 4.3.3 Multiple measurements via oversampling: Oversampled one-dimensional DFT measurements remained ill-posed: Fienup and PhaseLift produced data-fitting reconstructions far from the original solution.The average SNR was around 4dB for Fienup and only marginally better for PhaseLift.
4.4 2-D simulations
The 2-D simulations apply PhaseLift to complex-valued images using Gaussian or binary illuminations, recovering images from noiseless and noisy measurements. Oversampling alone remains severely ill-posed, with reconstructions that can fit the data while differing substantially from the true signal.
- Noiseless measurements: A 256 × 256 complex-valued goldballs image was recovered from noiseless measurements using three Gaussian illuminations, including one constant mask.The reconstruction was visually indistinguishable from the original.
- Noiseless measurements: Eight binary illuminations and more reweighting steps produced a reconstruction of comparable quality to the Gaussian-mask result.Binary masks use entries equal to 0 or 1 with equal probability.
- Noisy measurements: 11.83dB reconstructed SNR was obtained from 20dB noisy measurements, while 47.96dB was obtained from 60dB measurements using 32 Gaussian random masks.The 20dB reconstruction retained all visible image features, and the 60dB reconstruction was virtually indistinguishable from the original.
- Oversampling: Oversampling 2-D real nonnegative signals does not resolve phase-retrieval ambiguity, despite the use of PhaseLift and Fienup’s algorithm.The experiments use 128 × 128 images and oversampling rates from 2 to 5.
- Oversampling: PhaseLift can achieve small relative residual error while producing reconstructions far from the true signal, indicating an ill-conditioned problem.Fienup’s iterates also often stagnated and produced reconstructions dependent on the initial random guess.
5 Discussion
The discussion presents the framework as promising while identifying unresolved theoretical, algorithmic, and experimental limitations. In particular, oversampling can remain severely ill-posed, and the method’s robustness and physical implementation require further study.
- Open problems: The framework combines multiple illuminations with convex optimization but still calls for improved theory, algorithms, and physical experiments on real data.The authors describe physical implementation and testing on real data as future work.
- Oversampling limitations: The table illustrates severe ill-posedness: PhaseLift fits measured data well while its reconstructions can still have large error, unlike reliable recovery of the true signal.Fienup’s algorithm may also fail to satisfy the data and support constraints simultaneously.
- Theoretical limitations: The theory does not yet establish which physically implementable illuminations ensure trace-norm recovery, how many patterns suffice, or whether noise robustness can be proved.The paper reports graceful empirical degradation as SNR decreases but asks whether this can be made rigorous.
- Algorithmic limitations: Lifting creates potentially enormous optimization problems, motivating algorithms that exploit low rank without assembling or storing very large matrices.The authors identify randomized matrix sketches as a possible direction.
- Oversampling limitations: Oversampling appears extremely problematic in practice because distinct 2-D signals can have nearly coincident Fourier magnitudes despite increased sampling.The discussion also notes that common algorithms may return solutions that vary with the initial guess.