Super Resolution Phase Retrieval for Sparse Signals

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

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: i) we leverage the finite rate of innovation sampling theory to super-resolve the auto-correlation function from a limited number of samples, ii) we design a greedy algorithm that identifies the locations of a sparse solution given the super-resolved auto-correlation function, iii) 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.

Introduction

Phase Retrieval (PR) is a fundamental challenge in imaging and optical applications, such as X-ray crystallography and astronomy. In these domains, physical sensors often only capture the intensity (magnitude) of a signal's Fourier transform, while the phase information is lost. Mathematically, this task is equivalent to recovering a signal from its auto-correlation function (ACF).

Most existing PR algorithms operate on a discrete grid. However, physical signals—such as the arrangement of atoms in a molecule—exist in a continuous space. Discretizing this space introduces "off-grid" errors and fundamentally limits the achievable resolution. This paper addresses the challenge of recovering the exact continuous locations and amplitudes of a sparse signal from a limited number of noisy Fourier magnitude samples.

Methodology: A Three-Stage Pipeline

The proposed framework avoids the limitations of grid-based methods by modeling the signal as a sum of Diracs in a continuous domain. The reconstruction process follows a modular three-stage pipeline:

  1. ACF Super Resolution: The measured Fourier intensities are treated as discrete samples of the Fourier transform of the signal's ACF. By applying Finite Rate of Innovation (FRI) sampling theory, the continuous-domain ACF is reconstructed. This step identifies the "unlabeled differences" between all pairs of points in the signal.
  2. Support Recovery: Recovering point locations from a set of unlabeled differences is a combinatorial challenge known as the Turnpike Problem. The authors developed a greedy algorithm that starts with the largest difference and iteratively adds points that best fit the remaining measured differences. To manage computational costs, a "caching" mechanism was introduced, reducing complexity from $O(K^6)$ to approximately $O(K^5)$.
  3. Amplitude Recovery: With locations established, the individual atom amplitudes are recovered using an algebraic approach based on matrix completion. By transforming ACF amplitudes into a log-domain matrix, the system solves for amplitudes without requiring complex matrix inversions.
The three-stage pipeline for super-resolution phase retrieval, moving from discrete samples to a continuous-domain reconstruction.

Experimental Evaluation and Key Insights

The algorithm was rigorously evaluated using synthetic 1D and 2D sparse signals consisting of $K$ Diracs with varying locations and amplitudes. Performance was tested under different noise models, including additive Gaussian noise on both point locations and Fourier coefficients.

Key Results

  • Superiority over Charge Flipping: In simulations with $K=5$ atoms, the proposed method achieved significantly lower reconstruction errors compared to Charge Flipping, a standard iterative algorithm in crystallography, particularly in low-to-moderate noise regimes (SNR > 10dB).
  • Exact Recovery: In noiseless scenarios, the algorithm achieves mathematically exact reconstruction of continuous locations, whereas grid-based methods remain limited by bin size.
  • Noise Resilience: By incorporating "denoising of partial solutions"—averaging multiple realizations of the same difference—the average $l_2$ error was reduced by up to 62% over the basic greedy version.

Phase Transitions

A critical finding of the theoretical analysis is the existence of a "sharp phase transition." The algorithm performs almost perfectly up to a specific noise threshold, after which the probability of success drops rapidly. This behavior was validated empirically, showing a strong alignment between theoretical bounds and experimental results.

Theoretical and empirical phase transitions showing the probability of success P(σ, K) as a function of noise level σ and sparsity K.

Conclusion

By leveraging sparsity as a strong prior, this framework transforms an ill-posed problem into a well-posed one with a unique solution (up to trivial shifts and reflections). While the $O(K^5)$ complexity remains a bottleneck for signals with a very large number of atoms, the ability to perform super-resolution in a continuous domain represents a significant advancement over traditional discrete approximations. Future work will focus on handling "collisions" (where multiple pairs of points share the same distance) and extending the model to non-point-like scattering functions.

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: i) we leverage the finite rate of innovation sampling theory to super-resolve the auto-correlation function from a limited number of samples, ii) we design a greedy algorithm that identifies the locations of a sparse solution given the super-resolved auto-correlation function, iii) 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},
}
Figure