Robust Phase Retrieval with the Swept Approximate Message Passing (prSAMP) Algorithm

Boshra Rajaei, Sylvain Gigan, Florent Krzakala, Laurent Daudet

Abstract

Phase retrieval is a critical challenge in optical imaging where detectors capture only intensity, losing phase information. While Approximate Message Passing (AMP) algorithms offer high performance, they often struggle with ill-conditioned measurement matrices typical of real-world hardware. This paper introduces prSAMP (Phase Retrieval Swept Approximate Message Passing), which utilizes a sequential update strategy to achieve robust convergence. We evaluate prSAMP against synthetic benchmarks, demonstrating its stability and effectiveness in recovering complex signals from magnitude-only measurements, even in the presence of noise and ill-conditioned matrices.

Introduction

In many imaging fields—from X-ray crystallography to astronomy—detectors can only measure the intensity (magnitude) of light, losing the phase information entirely. This is the "Phase Retrieval" problem: reconstructing a signal $x$ from measurements $y = |Hx + w|^2$. While several algorithms exist to solve this, they often rely on "well-behaved" measurement matrices, such as i.i.d. Gaussian matrices.

However, real-world optical setups often use binary spatial light modulators (SLMs) or digital micromirror devices (DMDs) to shape wavefronts, resulting in "ill-conditioned" matrices. In these scenarios, standard algorithms like PhaseLift or even the faster Approximate Message Passing (AMP) often fail to converge or get stuck in local minima. The prSAMP algorithm aims to bridge the gap between high-performance signal processing theory and the messy reality of optical hardware.

Methodology

The prSAMP algorithm merges two powerful ideas: Generalized AMP (GAMP) and Swept AMP (SwAMP). GAMP provides a Bayesian framework that handles non-linear "output channels" (the magnitude-only measurement), while SwAMP replaces standard parallel updates with a sequential "swept" approach. Instead of updating all variables simultaneously, SwAMP updates them one by one in a random or sequential order. This "sweeping" significantly stabilizes the algorithm, preventing the oscillations that typically cause AMP to fail on difficult matrices.

Flowchart of the prSAMP algorithm illustrating the iterative update cycle for signal estimation.

The algorithm incorporates specific mathematical priors to guide recovery:

  • Gaussian Prior: Used for calibration steps where the signal is complex.
  • Binary Prior: Used for reconstruction steps where the input signal is known to be binary (0 or 1).
  • 2D Damping: A spatial smoothing step using local medians to ensure recovered images maintain structural integrity rather than appearing as random noise.

Experimental Setup and Results

The algorithm was evaluated using synthetic benchmarks designed to mimic real-world optical challenges, including Random Bernoulli Binary Matrices (simulating DMDs) and Gaussian i.i.d. Matrices as a baseline. Simulations included varying levels of Signal-to-Noise Ratio (SNR) from 30 dB down to 5 dB.

Key Insights

  • Stability through Sequential Updates: The instability of message passing on ill-conditioned matrices is largely a synchronization issue. By updating variables sequentially, the algorithm avoids the divergent feedback loops common in parallel updates.
  • The 4N Rule: Results confirm a theoretical threshold: to uniquely recover a dense complex signal of size $N$, at least $M \ge 4N$ measurements are generally required. However, by using a binary prior, prSAMP can achieve complete recovery with significantly fewer measurements ($M \approx N$).
  • Phase Transition Success: Phase transition plots show a clear boundary where prSAMP succeeds in recovering signals that cause other AMP variants to fail. The algorithm remains effective even under high noise (5 dB SNR), though it requires more measurements to compensate.

Discussion and Conclusion

While prSAMP offers superior stability, it introduces a computational trade-off. The sequential nature makes the algorithm $O(N^3)$, which is slower than parallel versions. To mitigate this, a "block-based" approach—splitting the image into smaller tiles—can be used to manage complexity for real-time imaging.

Additionally, like all phase retrieval methods, the signal can only be recovered up to a "global phase shift," requiring a final tuning step. Future work may involve integrating more sophisticated 2D priors, such as Restricted Boltzmann Machines, to improve the recovery of complex natural textures and patterns. In summary, prSAMP provides a robust, hardware-compatible solution for phase retrieval in challenging optical environments.

Summary updated

Abstract

In phase retrieval, the goal is to recover a complex signal from the magnitude of its linear measurements. While many well-known algorithms guarantee deterministic recovery of the unknown signal using i.i.d. random measurement matrices, they suffer serious convergence issues for some ill-conditioned measurement matrices. As an example, this happens in optical imagers using binary intensity-only spatial light modulators to shape the input wavefront. The problem of ill-conditioned measurement matrices has also been a topic of interest for compressed sensing researchers during the past decade. In this paper, using recent advances in generic compressed sensing, we propose a new phase retrieval algorithm that well-behaves for a large class of measurement matrices, including Gaussian and Bernoulli binary i.i.d. random matrices, using both sparse and dense input signals. This algorithm is also robust to the strong noise levels found in some imaging applications.
BibTeX
@article{rajaei2017robust,
  author = {Boshra Rajaei and Sylvain Gigan and Florent Krzakala and Laurent Daudet},
  title = {{Robust Phase Retrieval with the Swept Approximate Message Passing (prSAMP) Algorithm}},
  journal = {Image Process. Line},
  year = {2017},
  doi = {10.5201/ipol.2017.178},
}
Figure