Adversarial Phase Retrieval via Nonlinear Least Absolute Deviation

Gao Huang, Li Song, Hang XuarXiv 2023 · DOI · arXiv

TL;DR

This paper establishes the theoretical limits of "adversarial phase retrieval"—the task of recovering a signal from magnitude-only measurements even when a malicious actor corrupts a significant portion of the data. The researchers prove that amplitude-based models are nearly twice as robust as intensity-based ones, tolerating up to 20.43% adversarial outliers compared to just 11.85%.

What Problem Does This Paper Address?

Phase retrieval is a cornerstone of modern imaging, essential for fields like X-ray crystallography, astronomy, and microscopy. In these applications, sensors often only capture the magnitude (amplitude or intensity) of a signal, losing the phase information. Mathematically, we try to recover a signal $x_0$ from measurements $b_i \approx |\langle a_i, x_0 \rangle|^k$, where $k=1$ for amplitude and $k=2$ for intensity.

While standard algorithms work well with "nice" Gaussian noise, they crumble in the face of adversarial outliers. These are corruptions that aren't just random; they can be arbitrarily large and strategically chosen based on the signal or the measurement system itself (e.g., sensor failure or targeted interference).

The authors set out to answer a fundamental question: Which measurement model is more robust to these attacks, and exactly how much corruption can they stand before recovery becomes impossible?

Methods

The authors employ the Nonlinear Least Absolute Deviation (LAD) approach. Unlike standard least-squares (which uses $\ell_2$-loss and is sensitive to outliers), LAD uses $\ell_1$-loss, which is known for its robustness in linear regression but is much harder to analyze in the nonlinear world of phase retrieval.

Key technical contributions include:

  1. Nonlinear ROB Condition: They developed a "Nonlinear Robust Outlier Bound" (ROB) framework to characterize the worst-case scenario for corrupted measurements.
  2. Novel Statistical Analysis: To find the exact "breaking point" of these models, the authors derived new probability density functions (PDFs) for the combination of two non-independent Gaussian random variables. This allowed them to calculate the exact distribution of the error terms.
  3. Sharp Threshold Construction: They didn't just find a lower bound; they constructed "adaptive counterexamples"—specific adversarial attacks that cause recovery to fail exactly at the predicted limits—proving their thresholds are theoretically "sharp."

Datasets

As a theoretical work, the paper primarily uses synthetic data to validate its proofs:

  • Design Vectors: i.i.d. standard Gaussian vectors $\{a_i\}$.
  • Ground Truth: Standard Gaussian signal $x_0 \in \mathbb{R}^5$.
  • Sample Size: Experiments were conducted with $m = 500n$ (where $n$ is signal dimension) to observe asymptotic behavior.
  • Corruption: Adversarial outliers were generated following the specific counterexample logic derived in the proofs to test the limits of the model.

Key Insights and Ideas

  • The Amplitude Advantage: The most significant finding is that amplitude-based models ($|Ax|$) are fundamentally more robust than intensity-based models ($|Ax|^2$). Squaring the measurements in the intensity model effectively "amplifies" the influence of outliers, making it easier for an adversary to derail the reconstruction.
  • Phase Transitions: The paper demonstrates a clear "phase transition" in robustness. Below the threshold ($s^*$), the signal can be recovered with high accuracy; immediately above it, the error jumps dramatically, and the ground truth is lost.
  • Independence is Not Required: A major hurdle in previous literature was the assumption that noise or outliers were independent of the measurements. This paper removes that crutch, proving that LAD remains effective even when the adversary knows your measurement matrix and signal.

Key Results

The authors derived two specific "sharp sparsity thresholds" ($s^*$):

  • Amplitude-based LAD: Can tolerate up to $s^{*,1} \approx 0.2043$ (roughly 20.4% of measurements corrupted).
  • Intensity-based LAD: Can tolerate up to $s^{*,2} \approx 0.1185$ (roughly 11.9% of measurements corrupted).

Numerical experiments (Figure 2 in the paper) confirm these values perfectly, showing the relative error staying near zero until the fraction of corruption hits these exact percentages, at which point the error spikes to 1.0 (total failure).

Limitations and Future Work

  • Gaussian Assumption: The proofs rely on the measurement vectors $\{a_i\}$ being standard Gaussian. In real-world optics, measurements are often structured (e.g., Coded Diffraction Patterns or Fourier transforms), and it remains to be seen if these exact thresholds hold for those matrices.
  • Computational Complexity: While the paper proves the existence of a robust solution via the LAD objective, solving that objective in high dimensions can be computationally expensive. The authors mention algorithms like Wirtinger flow, but a deep dive into the most efficient optimization path for adversarial LAD is a natural next step.
  • Complex Signals: The current analysis focuses on real-valued signals. Extending these sharp thresholds to the complex domain ($\mathbb{C}^n$) would be highly relevant for physical applications like holography.

Summary updated

Abstract

We investigate the phase retrieval problem perturbed by dense bounded noise and sparse outliers that can change an adversarially chosen $s$-fraction of the measurement vector. The adversarial sparse outliers may exhibit dependence on both the observation and the measurement. We demonstrate that the nonlinear least absolute deviation based on amplitude measurement can tolerate adversarial outliers at a fraction of $s^{*,1}\approx0.2043$, while the intensity-based model can tolerate a fraction of $s^{*,2}\approx0.1185$. Furthermore, we construct adaptive counterexamples to show that the thresholds are theoretically sharp, thereby showing the presentation of phase transition in the adversarial phase retrieval problem when the corruption fraction exceeds the sharp thresholds. This implies that the amplitude-based model exhibits superior adversarial robustness in comparison with the intensity-based model. Corresponding experimental results are presented to further illustrate our theoretical findings. To the best of our knowledge, our results provide the first theoretical examination of the distinction in robustness performance between amplitude and intensity measurement. A crucial point of our analysis is that we explore the exact distribution of some combination of two non-independent Gaussian random variables and present the novel probability density functions to derive the sharp thresholds.
BibTeX
@misc{huang2023adversarial,
  author = {Gao Huang and Li Song and Hang Xu},
  title = {{Adversarial Phase Retrieval via Nonlinear Least Absolute Deviation}},
  year = {2023},
  eprint = {2312.06190},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.06190},
}
Figure