Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption

Jinghui Chen, Lingxiao Wang, Xiao Zhang, Quanquan Gu

Introduction

In many high-resolution imaging applications, such as X-ray crystallography, diffraction imaging, and microscopy, physical sensors are limited to capturing only the intensity (magnitude) of a signal, while the phase information is lost. Reconstructing the original signal from these magnitude-only measurements is a fundamental challenge known as the phase retrieval problem. Mathematically, this involves solving a system of quadratic equations. While algorithms like Wirtinger Flow (WF) have successfully addressed this problem under clean conditions, real-world data is frequently plagued by "arbitrary corruption"—massive outliers caused by sensor malfunctions, occlusions, or recording errors that deviate significantly from standard Gaussian noise.

The Challenge of Arbitrary Corruption

Standard phase retrieval algorithms are highly sensitive to outliers. Even a small percentage of corrupted measurements can lead to a total failure in signal recovery. Previous attempts to build robustness, such as Median-Truncated Wirtinger Flow (Median-TWF), often relied on discarding suspicious data points. However, these methods typically require a high sample complexity—often $O(n \log n)$—to guarantee recovery, making them computationally expensive and less efficient for large-scale, high-dimensional problems.

The Robust Wirtinger Flow (Robust-WF) Framework

This paper introduces Robust Wirtinger Flow (Robust-WF), a nonconvex algorithm designed to achieve optimal sample complexity and linear convergence even in the presence of massive, arbitrary corruption. Unlike previous methods that treat outliers as data to be ignored, Robust-WF treats corruption as a variable to be explicitly estimated.

The algorithm operates in two distinct stages:

  1. Robust Initialization: The process begins with a "hard thresholding" step to identify and temporarily isolate the largest outliers. A spectral method is then applied to this filtered data to generate a high-quality initial guess for the signal.
  2. Joint Gradient Descent: Rather than using a standard squared-error loss function, Robust-WF employs a reshaped amplitude-based loss function. This approach is inherently more stable against the heavy tails of Gaussian measurements. Crucially, at each iteration, the algorithm performs a joint update: it refines the estimate of the signal ($\mathbf{x}$) while simultaneously updating an estimate of the sparse corruption vector ($\eta$).

By modeling the corruption explicitly, the algorithm utilizes all available information, ensuring that uncorrupted samples with naturally large magnitudes are not mistakenly discarded.

Theoretical and Computational Advantages

Robust-WF offers several key theoretical breakthroughs:

  • Optimal Sample Complexity: The algorithm requires only $O(n)$ measurements, where $n$ is the signal dimension. This is the theoretical "gold standard" for efficiency and an improvement over the $O(n \log n)$ requirements of previous robust solvers.
  • Linear Convergence: The authors provide mathematical proof that the algorithm converges at a linear rate to the true signal, up to the level of the background noise.
  • Computational Efficiency: Despite its added robustness, the computational cost remains $O(mn \log(1/\epsilon))$, matching the speed of non-robust state-of-the-art methods.

Experimental Validation

The authors validated Robust-WF using both synthetic high-dimensional data and real-world benchmark images under the Coded Diffraction Pattern (CDP) model. Tests were conducted on classic images including Lenna ($512 \times 512$), Stanford ($1280 \times 320$), and Galaxy ($1920 \times 1080$).

The results demonstrate significant resilience:

  • Outlier Tolerance: Robust-WF successfully recovered signals even when 30% of the data was corrupted. In contrast, standard Wirtinger Flow methods typically fail when corruption exceeds 5%.
  • Precision: On the "Galaxy" image benchmark, Robust-WF achieved a relative recovery error of $2.75 \times 10^{-12}$, outperforming Median-TWF by two orders of magnitude.

Conclusion

Robust Wirtinger Flow represents a significant step forward in making phase retrieval practical for real-world sensing environments. By shifting the paradigm from outlier rejection to joint estimation, Robust-WF achieves the theoretical limits of sample complexity without sacrificing computational speed. Future work will focus on refining the mathematical proofs to remove remaining logarithmic factors and extending the framework to non-Gaussian measurement models.

Summary updated

Abstract

We consider the robust phase retrieval problem of recovering the unknown signal from the magnitude-only measurements, where the measurements can be contaminated by both sparse arbitrary corruption and bounded random noise. We propose a new nonconvex algorithm for robust phase retrieval, namely Robust Wirtinger Flow to jointly estimate the unknown signal and the sparse corruption. We show that our proposed algorithm is guaranteed to converge linearly to the unknown true signal up to a minimax optimal statistical precision in such a challenging setting. Compared with existing robust phase retrieval methods, we achieve an optimal sample complexity of $O(n)$ in both noisy and noise-free settings. Thorough experiments on both synthetic and real datasets corroborate our theory.
BibTeX
@misc{chen2017robust,
  author = {Jinghui Chen and Lingxiao Wang and Xiao Zhang and Quanquan Gu},
  title = {{Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption}},
  year = {2017},
  eprint = {1704.06256},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1704.06256},
}
Figure