Super Resolution Phase Retrieval for Sparse Signals

Gilles Baechler, Miranda Krekovic, Juri Ranieri, Amina Chebira, Yue M. Lu, Martin Vetterli

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:

  1. 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.
  2. 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)$.
  3. 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

Abstract

In a variety of fields, in particular those involving imaging and optics, we often measure signals whose phase is missing or has been irremediably distorted. Phase retrieval attempts to recover the phase information of a signal from the magnitude of its Fourier transform to enable the reconstruction of the original signal. Solving the phase retrieval problem is equivalent to recovering a signal from its auto-correlation function. In this paper, we assume the original signal to be sparse; this is a natural assumption in many applications, such as X-ray crystallography, speckle imaging and blind channel estimation. We propose an algorithm that resolves the phase retrieval problem in three stages, first, we leverage the finite rate of innovation sampling theory to super-resolve the auto-correlation function from a limited number of samples, second, we design a greedy algorithm that identifies the locations of a sparse solution given the super-resolved auto-correlation function, finally, we recover the amplitudes of the atoms given their locations and the measured auto-correlation function. Unlike traditional approaches that recover a discrete approximation of the underlying signal, our algorithm estimates the signal on a continuous domain, which makes it the first of its kind. Along with the algorithm, we derive its performance bound with a theoretical analysis and propose a set of enhancements to improve its computational complexity and noise resilience. Finally, we demonstrate the benefits of the proposed method via a comparison against Charge Flipping, a notable algorithm in crystallography.
BibTeX
@article{baechler2019super,
  author = {Gilles Baechler and Miranda Krekovic and Juri Ranieri and Amina Chebira and Yue M. Lu and Martin Vetterli},
  title = {{Super Resolution Phase Retrieval for Sparse Signals}},
  journal = {IEEE Trans. Signal Process.},
  year = {2019},
  url = {https://openreview.net/forum?id=zSaI5zvntH1},
}

Loading related content...

Figure