Solving a perturbed amplitude-based model for phase retrieval

Bing Gao, Yang Wang, Zhiqiang XuarXiv 2019 · arXiv

Reconstructing a signal from only the magnitude of its measurements—discarding the phase—is a classic challenge known as phase retrieval. This problem is ubiquitous in fields ranging from X-ray crystallography to astronomical imaging. While recent non-convex algorithms have made significant strides in solving this efficiently, they often rely on complex "hacks" like truncation or re-weighting to maintain mathematical stability.

In their paper "Perturbed amplitude flow for phase retrieval," researchers Bing Gao, Xinwei Sun, Yang Wang, and Zhiqiang Xu introduce a surprisingly simple fix: a mathematical "nudge" that smooths out the objective function, leading to an algorithm that is both theoretically optimal and practically faster.

The Perturbed Amplitude-Based Model

The core innovation is the Perturbed Amplitude Flow (PAF) algorithm. In standard phase retrieval, we seek a vector $x$ given measurements $b_j = |a_j^* x|$. Because phase information is lost, the problem is inherently non-convex.

Instead of minimizing the standard distance between amplitudes, which can lead to "bad" gradients when the estimate is nearly orthogonal to a measurement vector, PAF minimizes a perturbed loss function:

$$\min_z f_\epsilon(z) := \frac{1}{m} \sum_{j=1}^m \left( \sqrt{|a_j^* z|^2 + \epsilon_j^2} - \sqrt{b_j^2 + \epsilon_j^2} \right)^2$$

Here, $\epsilon_j = \sqrt{\alpha} b_j$ is a small perturbation term. This simple modification ensures the objective function is smooth everywhere, preventing the gradient's denominator from hitting zero. Consequently, PAF avoids the need for manual truncation (discarding outliers) or complex re-weighting schemes used in previous state-of-the-art methods like Truncated Amplitude Flow (TAF).

Theoretical and Practical Advantages

PAF offers several key advantages:

  • Smoothness and Unified Theory: The smooth nature of the loss function allows for a unified theoretical framework. The authors proved linear convergence for both real and complex signals, a task that has historically been difficult for non-smooth models.
  • Optimal Complexity: PAF achieves exact recovery with $O(n)$ measurements, reaching the information-theoretic limit.
  • Simplicity: By using vanilla gradient descent (Wirtinger derivative) after a standard spectral initialization, the algorithm remains easy to implement and computationally efficient.

Empirical Results

The authors validated PAF using synthetic Gaussian data, natural images (e.g., the "Milky Way Galaxy"), and Coded Diffraction Patterns (CDP).

Linear Convergence

In noiseless environments, PAF demonstrates exponential decay in relative error. As shown in the figure below, PAF (red circles) converges significantly faster than standard Wirtinger Flow (WF) and reaches machine precision within approximately 100-200 iterations.

Relative error vs iteration count in the noiseless case, showing PAF's superior convergence rate.

Success Rate and Robustness

PAF exhibits a high empirical success rate even with a low number of measurements ($m/n \approx 2$ to $3$). It outperforms standard Amplitude Flow (AF) and remains competitive with truncated methods.

Recovery probability for real and complex signals vs. oversampling ratio m/n.

Furthermore, in image recovery tasks, PAF proved to be significantly faster than Truncated Wirtinger Flow (TWF). For instance, recovering the Milky Way image to a relative error of $10^{-5}$ took PAF approximately 97 seconds, compared to 320 seconds for TWF. The algorithm also maintains stability under Gaussian noise, converging reliably to a solution.

Limitations and Future Directions

The performance of PAF depends on the choice of the perturbation parameter $\alpha$. While the authors suggest a theoretically sound value of $\alpha \approx 0.826$, some application-specific tuning may be beneficial. Additionally, while empirical tests on Coded Diffraction Patterns were successful, extending the rigorous theoretical proofs from Gaussian measurements to the CDP model remains an open area for future research.

Summary updated

BibTeX
@misc{gao2019solving,
  author = {Bing Gao and Yang Wang and Zhiqiang Xu},
  title = {{Solving a perturbed amplitude-based model for phase retrieval}},
  year = {2019},
  eprint = {1904.10307},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.10307},
}
Figure