# Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems

arXiv: https://arxiv.org/abs/2205.13827 · HTML: https://mlsanity.com/paper/2205.13827/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 76 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 21 of 21)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery](https://mlsanity.com/paper/1603.08315/) (2016)
- [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016)
- [Learning without Concentration for General Loss Functions](https://mlsanity.com/paper/1410.3192/) (2014)
- [Nonconvex Matrix Factorization from Rank-One Measurements](https://mlsanity.com/paper/1802.06286/) (2018)
- [Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss](https://mlsanity.com/paper/2202.02063/) (2022)
- [The local convexity of solving systems of quadratic equations](https://mlsanity.com/paper/1506.07868/) (2015)
- [On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems](https://mlsanity.com/paper/2002.01066/) (2020)
- [An Oracle Gradient Regularized Newton Method for Quadratic Measurements Regression](https://mlsanity.com/paper/2202.09651/) (2022)
- [Phase Retrieval via Incremental Truncated Wirtinger Flow](https://mlsanity.com/paper/1606.03196/) (2016)

## Built on by (most cited first, 2 of 2)

- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [Robust Gradient Descent for Phase Retrieval](https://mlsanity.com/paper/2410.10623/) (2024)

## Abstract (arXiv)

In this paper, we study the estimation performance of empirical ℓ2 risk minimization (ERM) in noisy (standard) phase retrieval (NPR) given by yk = |αk^*x0|2+ηk, or noisy generalized phase retrieval (NGPR) formulated as yk = x0^*Akx0 + ηk, where x0∈mathbbKd 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 mathbbK=ℝ and mathbbK=mathbbC. In NPR under arbitrary noise vector η, we derive a new error bound Obig(|η|_∞√fracdn + frac|1^topη|nbig), which is tighter than the currently known one Obig(frac|η|√nbig) in many cases. In NGPR, we show Obig(|η|frac√dnbig) for arbitrary η. In both problems, the bounds for arbitrary noise immediately give rise to tildeO(√fracdn) 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 tildeObig(big[√fracdnbig]1-1/lbig) 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 Akk=1n in NGPR is more robust to biased noise than the rank-1 frame αkαk^*k=1n in NPR. Extensive experimental results are presented to illustrate our theoretical findings.