Robust phase retrieval with the swept approximate message passing (prSAMP) algorithm

Boshra Rajaei, Sylvain Gigan, Florent Krzakala, Laurent Daudet

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 with some ill-conditioned 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-adopts for both Gaussian i.i.d. and binary matrices using both sparse and dense input signals. This algorithm is also robust to the strong noise levels found in some imaging applications.

Introduction

Phase Retrieval (PR) is a fundamental challenge in imaging fields such as X-ray crystallography and optical microscopy, where detectors typically capture only the intensity (magnitude) of light, losing the phase information. While mathematical solutions exist, they often rely on idealized, well-behaved measurement matrices (e.g., Gaussian i.i.d.). In practical applications, particularly those utilizing Digital Micromirror Devices (DMDs) for wavefront shaping, measurement matrices are binary and frequently ill-conditioned. Standard PR algorithms often fail to converge under these realistic conditions, exhibiting instability or becoming trapped in local minima.

The prSAMP Algorithm

To address these challenges, we introduce prSAMP (phase retrieval Swept Approximate Message Passing). This algorithm builds upon the Bayesian framework of Approximate Message Passing (AMP) but introduces several key modifications to enhance stability and performance.

Swept Updates and Priors

The core innovation is the transition from parallel to sequential "swept" updates (SwAMP). By updating variables one by one in a randomized order rather than simultaneously, the algorithm achieves significantly higher stability when processing ill-conditioned, non-Gaussian matrices.

Flowchart of the prSAMP algorithm illustrating the iterative estimation of signal and variance.

The algorithm incorporates specialized priors:

  • Phase Retrieval Output Prior: Utilizes a Rician distribution-based function to handle magnitude-only measurements corrupted by Gaussian noise.
  • Tailored Input Priors: Employs Gaussian priors for calibration (complex signals, binary matrices) and binary priors for recovery (binary signals, complex matrices).
  • Spatial Damping: For 2D imaging, a damping mechanism mixes current estimates with local neighborhood medians to prevent convergence to local minima.

Experimental Results

The algorithm was evaluated using synthetic 1D and 2D signals to characterize its phase transitions and robustness to noise.

Performance and Robustness

In calibration scenarios (dense complex signal, $N=256$, 30 dB SNR), prSAMP consistently achieves recovery when the measurement ratio $M/N \ge 4$. For binary signal recovery, the required number of measurements is significantly lower, sometimes even $M < N$ depending on signal sparsity.

A critical strength of prSAMP is its graceful degradation under noise. As shown in the performance analysis, the algorithm maintains effective reconstruction even at low Signal-to-Noise Ratios (SNR).

Reconstruction performance (NMSE) of prSAMP as a function of the measurement ratio $\delta$ for various SNR levels.

Discussion and Future Work

The sequential nature of prSAMP, while providing stability, introduces a computational bottleneck with a complexity of $O(N^3)$. This limits its direct application in high-resolution, real-time imaging. Future research will focus on "block-based" approaches to parallelize the problem, potentially reducing complexity to $O(N^3/K^2)$ by solving smaller sub-problems independently. Despite these scaling challenges, prSAMP offers a robust solution for physical optical hardware where traditional methods falter.

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 some ill-conditioned 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-adopts for both Gaussian i.i.d. and binary 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