On Fienup Methods for Regularized Phase Retrieval

Edouard Pauwels, Amir Beck, Yonina C. Eldar, Shoham Sabach

Abstract

Alternating minimization, or Fienup methods, have a long history in phase retrieval. We provide new insights related to the empirical and theoretical analysis of these algorithms when used with Fourier measurements and combined with convex priors. In particular, we show that Fienup methods can be viewed as performing alternating minimization on a regularized nonconvex least-squares problem with respect to amplitude measurements. We then prove that under mild additional structural assumptions on the prior (semi-algebraicity), the sequence of signal estimates has a smooth convergent behaviour towards a critical point of the nonconvex regularized least-squares objective. Finally, we propose an extension to Fienup techniques, based on a projected gradient descent interpretation and acceleration using inertial terms. We demonstrate experimentally that this modification combined with an $\ell_1$ prior constitutes a competitive approach for sparse phase retrieval.

Introduction

Phase retrieval is a fundamental challenge in computational imaging, appearing in fields such as X-ray crystallography and astronomy. The problem involves reconstructing a signal from the magnitude of its Fourier transform, where the phase information is lost. Because this problem is inherently ill-posed, researchers typically incorporate "priors"—such as signal sparsity—to constrain the solution space. While the Fienup algorithm, an alternating minimization (AM) approach, has been a standard tool since the 1970s, it has historically lacked rigorous convergence guarantees and a clear framework for integration with modern sparse regularization.

Theoretical Framework and Methodology

This work bridges the gap between classical heuristics and modern optimization theory through three primary contributions:

  1. Optimization Interpretations: The authors demonstrate that Fienup methods are mathematically equivalent to Majorization-Minimization (MM) on a nonsmooth least-squares objective. Alternatively, they can be interpreted as Projected Gradient Descent (PGD) on a smooth convex objective subject to a nonconvex constraint set.
  2. Convergence Analysis: By utilizing the concept of semi-algebraicity—functions describable by polynomial inequalities—the authors prove that signal estimates in Fienup methods converge smoothly to a critical point, independent of the initial starting point.
  3. The FISTAPH Algorithm: Inspired by the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), the authors introduce FISTAPH (FISTA for PHase retrieval). This method incorporates an inertial momentum term into the Fienup iterations to accelerate convergence.

Experimental Evaluation

The proposed methods were evaluated using synthetic datasets of real-valued sparse signals with lengths $n \in \{64, 128, 256, 512\}$ and varying sparsity levels $K$ (5 to 25). White Gaussian noise was added to squared Fourier measurements at signal-to-noise ratios (SNR) ranging from 10 to 40. FISTAPH was benchmarked against standard Fienup variants (AM L0/L1), GESPAR, and Wirtinger Flow.

Key Results

The experiments yielded several critical insights:

  • Superior Accuracy: FISTAPH consistently achieved the highest probability of successful support recovery across all tested sparsity levels and noise conditions.
  • Computational Efficiency: FISTAPH demonstrated significant speedups. In larger signal regimes ($n=512$), it reached solutions in a fraction of the time required by second-order methods like Wirtinger Flow or combinatorial approaches like GESPAR.
  • Prior Selection: Interestingly, using a convex $\ell_1$ prior within the Fienup framework outperformed the non-convex $\ell_0$ (hard sparsity) prior in terms of recovery probability.
Support recovery probability across different SNR and signal lengths.
Median CPU usage for one simulation across different SNR and signal lengths.

Discussion and Future Work

The study highlights that Fienup methods naturally minimize objectives based on amplitude rather than intensity, which often yields better practical performance. While convergence was proven for standard Fienup methods, the theoretical convergence of the accelerated FISTAPH variant in a nonconvex setting remains an open question. Future research may also explore extending these Fourier-specific insights to general measurement matrices and high-dimensional 2D or 3D imaging data.

Summary updated

Abstract

Alternating minimization, or Fienup methods, have a long history in phase retrieval. We provide new insights related to the empirical and theoretical analysis of these algorithms when used with Fourier measurements and combined with convex priors. In particular, we show that Fienup methods can be viewed as performing alternating minimization on a regularized nonconvex least-squares problem with respect to amplitude measurements. We then prove that under mild additional structural assumptions on the prior (semi-algebraicity), the sequence of signal estimates has a smooth convergent behaviour towards a critical point of the nonconvex regularized least-squares objective. Finally, we propose an extension to Fienup techniques, based on a projected gradient descent interpretation and acceleration using inertial terms. We demonstrate experimentally that this modification combined with an $\ell_1$ prior constitutes a competitive approach for sparse phase retrieval.
BibTeX
@article{pauwels2018fienup,
  author = {Edouard Pauwels and Amir Beck and Yonina C. Eldar and Shoham Sabach},
  title = {{On Fienup Methods for Regularized Phase Retrieval}},
  journal = {IEEE Trans. Signal Process.},
  year = {2018},
  url = {https://openreview.net/forum?id=xT6tMDhtiF},
}
Figure