Source-linked AI summary
Phase Retrieval from Coded Diffraction Patterns
Emmanuel Candes, Xiaodong Li, Mahdi Soltanolkotabi
TL;DR
The paper addresses phase recovery from intensity-only measurements, motivated by settings such as X-ray imaging where detectors measure magnitudes rather than phases. It analyzes PhaseLift for physically inspired coded diffraction patterns and proves exact recovery with polylogarithmically many patterns, complemented by numerical experiments.
Problem
Phase retrieval seeks to recover an object from magnitude-only measurements, while Gaussian measurement models do not reflect data collected in X-ray imaging and related experiments.
Method
The paper models signal modulation followed by diffraction and analyzes PhaseLift as a semidefinite feasibility program, using an approximate dual certificate constructed through a golfing scheme.
Results
On the order of (log n)^4 coded diffraction patterns suffice for perfect recovery, with probability at least 1 − n^−γ when L ≥ cγ log^4 n.
Takeaways & Limitations
In a stylized physical setting, an arbitrary signal can be recovered from a fairly limited number of coded diffraction patterns by solving an SDP feasibility problem.
Takeaways & Limitations
The analysis assumes admissible modulations and imposes E[d^2] = 0 for exposition, while extensions to broader random modulations and removal of logarithmic factors remain unproved or open.
Abstract
from arXiv · showhide
This paper considers the question of recovering the phase of an object from intensity-only measurements, a problem which naturally appears in X-ray crystallography and related disciplines. We study a physically realistic setup where one can modulate the signal of interest and then collect the intensity of its diffraction pattern, each modulation thereby producing a sort of coded diffraction pattern. We show that PhaseLift, a recent convex programming technique, recovers the phase information exactly from a number of random modulations, which is polylogarithmic in the number of unknowns. Numerical experiments with noiseless and noisy data complement our theoretical analysis and illustrate our approach.
1 Introduction
The paper formulates phase retrieval for physically inspired coded diffraction measurements and analyzes PhaseLift under random modulations. It establishes exact recovery with a polylogarithmic number of coded diffraction patterns, supported by theory and numerical experiments.
- 1 Introduction: Phase retrieval seeks to recover missing phase information from magnitude-only measurements so the original signal can be reconstructed.
- 1 Introduction: X-ray imaging motivates the problem because detectors measure diffraction intensity, while the optical field is approximated by the object's Fourier transform.
- 1 Introduction: PhaseLift lifts phase retrieval to a Hermitian matrix problem and relaxes the rank constraint into a semidefinite program whose rank-one solution recovers x up to global phase.
- 1 Introduction: The paper replaces unrealistic Gaussian measurements with a physically inspired setup that modulates the signal before diffraction, producing coded diffraction patterns.
- 1 Introduction: Random modulation patterns make the PhaseLift solution exact with high probability once sufficiently many coded diffraction patterns are collected, reducing the feasible set to xx∗.
2 Numerical Experiments
The experiments evaluate PhaseLift across signal and measurement models, varying coded patterns and adding Poisson noise. Noiseless recovery succeeds with few coded patterns, while noisy reconstruction error tracks the noise level.
- Experimental setup: 50 trials use n = 128 random complex signals from low-pass and Gaussian models across four measurement models.The measurement models are Gaussian, binary, ternary, and octanary modulations or codes.
- Experimental setup: The convex program minimizes a squared data-fit term plus λtr(X), subject to X ⪰0, with λ = 10^-3.As λ tends to zero, this solution equals the optimal solution of the noiseless relaxation.
- Noiseless measurements: Six coded patterns are empirically sufficient for exact recovery across the studied signal and measurement models.A trial is successful when the relative reconstruction error falls below 10^-5.
- Noisy measurements: Poisson-noise experiments use eight coded diffraction patterns, ten repetitions per SNR level, and SNR values ranging from 10 to 50 dB.The regularization parameter is set to λ = 1/SNR, and the Poisson means equal the corresponding noiseless intensities.
- Noisy measurements: The average relative MSE degrades linearly as SNR decreases on a dB/dB scale, with an empirical slope near -1.This scaling means the MSE follows the noise level and is consistent with well-conditioned least-squares behavior.
3 Proofs
The proof establishes exact recovery by combining robust injectivity on a tangent space with an approximate dual certificate, using concentration inequalities and a golfing-scheme construction. With sufficiently many coded diffraction patterns, these conditions hold with high probability and make x x* the unique feasible point.
- Preliminaries: The admissibility model assumes bounded, symmetric modulation entries satisfying moment constraints, with E|d|^2 normalized to one.The modulation matrices are diagonal with independent copies of the admissible random variable on their diagonals.
- Preliminaries: The tangent space T is interpreted as the tangent space at xx* to the manifold of rank-one Hermitian matrices.Its orthogonal complement is handled through the corresponding projection onto T⊥.
- Recovery conditions: Lemma 3.6 shows that robust injectivity together with an approximate dual certificate makes xx* the unique feasible point.The proof decomposes a feasible perturbation into tangent and orthogonal components, then forces both components to vanish.
- Robust injectivity: L ≥ c log^3 n yields the robust-injectivity estimate on T with probability at least 1 − 1/(2n).This estimate is one of the concentration-based ingredients used to verify the recovery conditions.
- Dual certificate construction via the golfing scheme: The approximate dual certificate is constructed with the golfing scheme by partitioning the coded diffraction patterns into independent groups.The construction uses the independent groups iteratively and relies on Lemma 3.8 and matrix Hoeffding bounds.
- Dual certificate construction via the golfing scheme: The combined conditions hold with probability at least 1 − 1/(2n) when L ≥ c log^4 n for sufficiently large constants.The extra logarithmic factor arises from requiring both B ≥ c1 log n and Lb ≥ c2 log^3 n.
4 Discussion
The paper concludes that convex programming recovers signals from a few coded diffraction patterns generated by admissible random modulations. It proves an order-(log n)^4 pattern bound and identifies reducing this dependence as future work.
- 4 Discussion: Convex programming recovers a signal from a few diffraction patterns produced by generic modulations satisfying an admissibility condition.The result concerns exact recovery in the paper’s coded-diffraction setup.
- 4 Discussion: The proof shows that on the order of (log n)^4 coded diffraction patterns suffice for perfect recovery.The authors expect refinements could reduce this number, potentially to a figure independent of n.
5 Appendix
The appendix develops moment calculations for admissible complex modulation variables and records the resulting diagonal and off-diagonal cancellations. These identities support the expectation and concentration arguments used in the proofs.
- Moment calculations: The moment identities yield matrix expressions involving the modulation matrix D and the Fourier-related vectors fk.The appendix concludes these calculations after evaluating the surviving index configurations.
- Moment calculations: The appendix separates moment computations into diagonal terms with p = q and off-diagonal terms with p ≠ q.The stated conditions determine when the corresponding expectations vanish.
- Concentration: A diagonal matrix formed from independent variables Xℓ has E[Xℓ] = E[|d|^2] = 1 and |Xℓ| ≤ M^2.Hoeffding’s inequality combined with a union bound is then used to obtain the stated concentration result.