Error Bound of Empirical š“2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems

Junren Chen, Michael K. NgarXiv 2022 · DOI · arXiv

Abstract

In this paper, we study the estimation performance of empirical $\ell_2$ risk minimization (ERM) in noisy (standard) phase retrieval (NPR) given by $y_k = |α_k^*x_0|^2+η_k$, or noisy generalized phase retrieval (NGPR) formulated as $y_k = x_0^*A_kx_0 + η_k$, where $x_0\in\mathbb{K}^d$ is the desired signal, $n$ is the sample size, $η= (η_1,...,η_n)^\top$ is the noise vector. We establish new error bounds under different noise patterns, and our proofs are valid for both $\mathbb{K}=\mathbb{R}$ and $\mathbb{K}=\mathbb{C}$. In NPR under arbitrary noise vector $η$, we derive a new error bound $O\big(\|η\|_\infty\sqrt{\frac{d}{n}} + \frac{|\mathbf{1}^\topη|}{n}\big)$, which is tighter than the currently known one $O\big(\frac{\|η\|}{\sqrt{n}}\big)$ in many cases. In NGPR, we show $O\big(\|η\|\frac{\sqrt{d}}{n}\big)$ for arbitrary $η$. In both problems, the bounds for arbitrary noise immediately give rise to $\tilde{O}(\sqrt{\frac{d}{n}})$ for sub-Gaussian or sub-exponential random noise, with some conventional but inessential assumptions removed or weakened. In addition, we make a first attempt to ERM under heavy-tailed random noise assumed to have bounded $l$-th moment. To achieve a trade-off between bias and variance, we truncate the responses and propose a corresponding robust ERM estimator, which is shown to possess the guarantee $\tilde{O}\big(\big[\sqrt{\frac{d}{n}}\big]^{1-1/l}\big)$ in both NPR, NGPR. All the error bounds straightforwardly extend to the more general problems of rank-$r$ matrix recovery, and these results deliver a conclusion that the full-rank frame $\{A_k\}_{k=1}^n$ in NGPR is more robust to biased noise than the rank-1 frame $\{α_kα_k^*\}_{k=1}^n$ in NPR. Extensive experimental results are presented to illustrate our theoretical findings.

Introduction

Phase retrieval is a fundamental challenge in signal processing and imaging, appearing in applications such as X-ray crystallography and coherent diffractive imaging. In these settings, sensors typically capture only the intensity (magnitude) of a signal, losing the phase information. The goal is to reconstruct the original signal $x_0 \in \mathbb{K}^d$ from these magnitude-only measurements.

While many algorithms like Wirtinger Flow have been developed to solve this, the theoretical understanding of their performance in noisy environments—specifically how the reconstruction error scales with noise—has been incomplete. Previous error bounds were often loose, restricted to real-valued signals, or dependent on specific noise assumptions (like i.i.d. zero-mean Gaussian noise). This paper aims to "close the gap" by providing comprehensive error bounds for both standard (rank-1) and generalized (full-rank) phase retrieval under a wide variety of noise patterns.

Methodology

The authors analyze Empirical $\ell_2$ Risk Minimization (ERM), which seeks to find a signal that minimizes the sum of squared differences between observed and predicted measurements. They investigate two main models:

  1. Noisy Standard Phase Retrieval (NPR): Measurements are rank-1 quadratic forms: $y_k = |\alpha_k^*x_0|^2 + \eta_k$.
  2. Noisy Generalized Phase Retrieval (NGPR): Measurements use general Hermitian matrices: $y_k = x_0^*A_kx_0 + \eta_k$.

To derive their bounds, they employ sophisticated mathematical tools like Mendelson’s small ball method and covering arguments. A key contribution is the Robust ERM estimator designed for heavy-tailed noise. Instead of using raw measurements, they propose a truncation step—capping the responses $y_k$ at a certain threshold $\tau$—to prevent outliers from dominating the loss function, creating a strategic trade-off between bias and variance.

The findings are validated using extensive synthetic simulations involving complex Gaussian vectors (for NPR) and matrices (for NGPR), testing noise patterns ranging from deterministic sparse vectors to sub-Gaussian, sub-exponential, and heavy-tailed distributions.

Theoretical Results and Key Insights

The paper establishes a comprehensive set of error bounds, summarized in the tables below. A major insight is that the "spikiness" of the noise vector $\eta$ (how much its energy is concentrated in a few entries) determines the tightness of the bounds.

Standard Phase Retrieval (NPR)

For NPR under arbitrary noise, the authors achieve a new bound: $O\big(\|\eta\|_\infty\sqrt{\frac{d}{n}} + \frac{|\mathbf{1}^\top\eta|}{n}\big)$. This is tighter than the previously known $O\big(\frac{\|\eta\|}{\sqrt{n}}\big)$ in many cases, particularly for "low-spiky" noise common in real-world i.i.d. scenarios.

Table 1: Error Bounds for ERM in Noisy Standard Phase Retrieval (NPR)

Generalized Phase Retrieval (NGPR)

In NGPR, the authors establish a bound of $O\big(\|\eta\|\frac{\sqrt{d}}{n}\big)$ for arbitrary noise. A significant discovery is that full-rank measurement frames (NGPR) are inherently more robust to biased noise than rank-1 frames (NPR). In NGPR, the measurement matrices $A_k$ concentrate around zero, effectively "cancelling out" noise bias during optimization. This allows NGPR to achieve statistical consistency even with biased noise, whereas NPR generally cannot.

Table 2: Error Bounds for ERM in Noisy Generalized Phase Retrieval (NGPR)

Heavy-Tailed Noise and Matrix Recovery

For heavy-tailed noise with bounded $l$-th moments, the robust truncated estimator achieves an error rate of $\tilde{O}\big(\big[\sqrt{\frac{d}{n}}\big]^{1-1/l}\big)$. Furthermore, all established error bounds extend straightforwardly to the more general problem of rank-$r$ matrix recovery.

Conclusion and Future Work

This work provides a more rigorous theoretical foundation for ERM in phase retrieval, offering tighter bounds and robust estimation techniques. While it marks a significant step forward, limitations remain. The heavy-tailed bounds are currently signal-specific rather than uniform, and the rate optimality for such noise remains an open question. Additionally, while the paper focuses on the statistical properties of the global minimizer, the computational challenge of reaching this minimizer in a non-convex landscape continues to be an active area of research.

Summary updated

BibTeX
@misc{chen2022error,
  author = {Junren Chen and Michael K. Ng},
  title = {{Error Bound of Empirical š“2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems}},
  year = {2022},
  eprint = {2205.13827},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.13827},
}
Figure