Phase retrieval from power spectra of masked signals

Afonso S. Bandeira, Yutong Chen, Dustin G. MixonarXiv 2013 · OpenReview

TL;DR

This paper introduces a new method for reconstructing signals from their power spectra using a "polarization" technique with specially designed Fourier masks. This approach requires significantly fewer masks than existing methods like PhaseLift, leading to dramatically faster reconstruction times while maintaining comparable accuracy, especially in noisy conditions.

What Problem Does This Paper Address?

In many scientific fields, like X-ray diffraction imaging, we can easily measure the magnitude of a signal's Fourier transform (its power spectrum) but not its phase. Recovering the original signal from just the magnitudes is a notoriously difficult problem called "phase retrieval" because the phase information is lost. Traditional methods often rely on prior knowledge about the signal (like its shape or composition), but this isn't always available. A more recent approach involves using multiple measurements with different "masks" to introduce redundancy and uniquely determine the signal. However, finding an optimal set of masks that guarantees unique reconstruction and allows for efficient algorithms has been a challenge. This paper tackles this by constructing such a mask ensemble using a novel "polarization" method.

Methods

The core of this work is adapting a "polarization-based" phase retrieval technique, previously developed for general vector measurements, to the specific domain of Fourier masks. The key idea is to use a set of carefully constructed Fourier masks that, when applied to the signal before taking the power spectrum, allow for a unique reconstruction.

The authors leverage a concept from graph theory and additive combinatorics. They construct a graph where vertices represent combinations of masks and edges represent relationships between them. The "spectral gap" of this graph is crucial for ensuring unique signal recovery. They show that designing this graph with a large spectral gap is equivalent to finding a small set of numbers (a subset of $\mathbb{Z}_M$) with a small "Fourier bias."

They then use a probabilistic approach to construct this set, which leads to a method for generating the required Fourier masks. The number of masks needed is shown to be proportional to $O(\log M)$, where $M$ is the signal dimension. This is a significant reduction compared to methods that might require $O(M^2)$ measurements.

Datasets

Not discussed in the paper. The paper focuses on theoretical construction and numerical simulations rather than experiments on real-world datasets.

Key Insights and Ideas

  • Polarization for Fourier Masks: The paper demonstrates that the "polarization" technique, originally developed for general vector measurements, can be effectively adapted to the specific context of Fourier masks, opening up new possibilities for phase retrieval.
  • Graph Theory Connection: The problem of designing optimal masks is elegantly reframed as a problem in spectral graph theory, specifically finding graphs with large spectral gaps. This connection provides a powerful theoretical framework.
  • Additive Combinatorics and Fourier Bias: The authors show that the spectral gap of the constructed graph is directly related to the "Fourier bias" of a specific set derived from the masks. Minimizing Fourier bias becomes the key to achieving a good spectral gap.
  • Logarithmic Number of Masks: A major breakthrough is the theoretical result that only $O(\log M)$ Fourier masks are needed to uniquely determine a signal, a substantial improvement over previous methods.
  • Speed vs. Stability Trade-off: Numerical simulations reveal that while polarization offers a significant speed advantage, PhaseLift can sometimes achieve slightly better stability, particularly when given more masks.

Key Results

  • Theoretical Guarantee: The paper theoretically constructs an ensemble of $O(\log M)$ Fourier masks that uniquely determine any signal up to a global phase factor.
  • Computational Efficiency: Numerical simulations show that the polarization method is orders of magnitude faster than the state-of-the-art PhaseLift algorithm. For example, in noiseless scenarios, polarization can take minutes while PhaseLift takes hours for higher dimensional signals.
  • Comparable Stability: Despite the speed advantage, polarization exhibits comparable stability to PhaseLift, especially in noisy conditions. In some noisy scenarios, PhaseLift with more masks performs slightly better, but polarization remains a strong contender.
  • Noiseless Performance: In noiseless scenarios, polarization achieves near-perfect reconstruction (error ~ $10^{-14}$), significantly outperforming PhaseLift (~ $10^{-2}$).

Limitations and Future Work

  • Stability Proof: The authors acknowledge that while they establish injectivity and efficient recoverability, a rigorous proof of stable reconstruction from these Fourier masks is still needed.
  • Mask Count Optimization: The number of masks derived ($O(\log M)$) might be an artifact of the analysis and could potentially be reduced by leveraging additional signal information or better approximations.
  • Exploiting Fourier Structure: The paper suggests that the inherent Fourier structure of the masks was not fully exploited for further speedups, indicating a potential avenue for future research.
  • PhaseLift Guarantees: The authors express interest in seeking Fourier mask-based performance guarantees for PhaseLift and its modifications.

Summary updated

Abstract

In diffraction imaging, one is tasked with reconstructing a signal from its power spectrum. To resolve the ambiguity in this inverse problem, one might invoke prior knowledge about the signal, but phase retrieval algorithms in this vein have found limited success. One alternative is to create redundancy in the measurement process by illuminating the signal multiple times, distorting the signal each time with a different mask. Despite several recent advances in phase retrieval, the community has yet to construct an ensemble of masks which uniquely determines all signals and admits an efficient reconstruction algorithm. In this paper, we leverage the recently proposed polarization method to construct such an ensemble. We also present numerical simulations to illustrate the stability of the polarization method in this setting. In comparison to a state-of-the-art phase retrieval algorithm known as PhaseLift, we find that polarization is much faster with comparable stability.
BibTeX
@misc{bandeira2013phase,
  author = {Afonso S. Bandeira and Yutong Chen and Dustin G. Mixon},
  title = {{Phase retrieval from power spectra of masked signals}},
  year = {2013},
  eprint = {1303.4458},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1303.4458},
}
Figure