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:
- 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.
- 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