TL;DR
This paper introduces a novel three-stage framework to solve the phase retrieval problem—recovering a signal from only the magnitude of its Fourier transform—specifically for sparse signals in a continuous domain. By leveraging Finite Rate of Innovation (FRI) theory and a greedy support recovery algorithm, the authors achieve "super-resolution" reconstruction that outperforms traditional discrete, grid-based methods like Charge Flipping.
What Problem Does This Paper Address?
In many imaging and optical applications (like X-ray crystallography or astronomy), sensors can only measure the intensity (magnitude) of a signal's Fourier transform, while the phase information is lost. This is the Phase Retrieval (PR) problem. Mathematically, this is equivalent to recovering a signal from its auto-correlation function (ACF).
Most existing PR algorithms operate on a discrete grid. However, real-world signals (like atoms in a molecule) exist in continuous space. Discretizing the space leads to "off-grid" errors and limits resolution. The challenge addressed here is: How can we recover the exact continuous locations and amplitudes of a sparse signal from a limited number of noisy Fourier magnitude samples?
Methods
The authors propose a modular, three-stage pipeline:
- ACF Super Resolution: The measured Fourier intensities are samples of the Fourier transform of the signal's ACF. The authors use Finite Rate of Innovation (FRI) sampling theory to reconstruct the continuous-domain ACF from these discrete samples. This allows them to identify the "unlabeled differences" between all pairs of points in the signal.
- Support Recovery (The Greedy Approach): Recovering point locations from unlabeled differences is known as the Turnpike Problem. The authors design a greedy algorithm (Algorithm 1) that starts with the largest difference and iteratively adds points that best fit the remaining measured differences. They also introduce a "caching" mechanism to reduce the computational complexity from $O(K^6)$ to approximately $O(K^5)$.
- Amplitude Recovery: Once the locations are known, the authors use a clever algebraic approach based on matrix completion. By transforming the ACF amplitudes into a log-domain matrix, they can solve for the individual atom amplitudes without needing complex matrix inversions.
Datasets
The paper primarily uses synthetic datasets to rigorously evaluate the algorithm's performance:
- 1D and 2D Sparse Signals: Randomly generated sets of $K$ Diracs (atoms) with varying locations and amplitudes.
- Noise Models: Additive Gaussian noise is applied to both the point locations (to test support recovery) and the Fourier coefficients (to test the full pipeline).
- Benchmark: The proposed method is compared against Charge Flipping, a standard iterative algorithm used in crystallography.
Key Insights and Ideas
- Continuous vs. Discrete: By modeling the signal as a sum of Diracs in a continuous domain, the algorithm avoids the resolution limits imposed by a pixel grid.
- Symmetry as a Tool: The ACF is inherently symmetric. The authors exploit this by using a symmetric cost function in their greedy search, which significantly improves resilience to noise.
- The Power of Sparsity: Sparsity acts as a strong prior that turns an ill-posed problem (infinitely many signals can fit a Fourier magnitude) into a well-posed one with a unique solution (up to trivial shifts and reflections).
- Phase Transitions: The authors derive a theoretical bound for the probability of success. They show that the algorithm exhibits a "sharp phase transition"—it works almost perfectly up to a certain noise threshold, after which performance drops off rapidly.
Key Results
- Superiority over Charge Flipping: In simulations with $K=5$ atoms, the proposed algorithm achieved significantly lower reconstruction errors than Charge Flipping, especially in low-to-moderate noise regimes (SNR > 10dB).
- Exact Recovery: In noiseless scenarios, the algorithm achieves mathematically exact reconstruction of the continuous locations, whereas grid-based methods are always limited by their bin size.
- Noise Resilience: By incorporating "denoising of partial solutions" (averaging multiple realizations of the same difference), the authors reduced the average $l_2$ error by up to 62% compared to the basic greedy version.
Limitations and Future Work
- Computational Complexity: The $O(K^5)$ complexity makes the algorithm expensive for signals with a very large number of atoms ($K$). While much better than an exhaustive search, it remains a bottleneck for high-complexity 3D structures.
- Collisions: The algorithm assumes that the differences between points are distinct. If multiple pairs of points have the same distance (a "collision"), the support recovery becomes much more difficult.
- Future Directions: The authors suggest exploring more sophisticated ways to handle circular auto-correlations and extending the framework to handle non-point-like kernels (scattering functions) more robustly.
Summary updated