Error Bound of Empirical ${\ell }_2$ Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems

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=|{\alpha }_k^{\ast }{x}_0{|}^2+{\eta }_k$, or noisy generalized phase retrieval (NGPR) formulated as $y_k=x_0^{\ast }{A}_k{x}_0+{\eta }_k$, where $x_0\in {\mathbb{K}}^d$ is the desired signal, $n$ is the sample size, $\eta =({\eta }_1,...,{\eta }_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 $\eta$, we derive a new error bound $O(\Vert \eta {\Vert }_{\infty }\sqrt{\frac{d}{n}}+\frac{|1^{\top }\eta |}{n})$, which is tighter than the currently known one $O\left(\frac{\Vert \eta \Vert }{\sqrt{n}}\right)$ in many cases. In NGPR, we show $O(\Vert \eta \Vert \frac{\sqrt{d}}{n})$ for arbitrary $\eta$. 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 (e.g., independent or zero-mean condition) 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}\left(\right[\sqrt{\frac{d}{n}}{]}^{1-1/l})$ 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 $\{{\alpha }_k{\alpha }_k^{\ast }{\}}_{k=1}^n$ in NPR. Extensive experimental results are presented to illustrate our theoretical findings.

44 pages, 6 figures