# A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 7 Sep 2024.

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

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016)
- [Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points](https://mlsanity.com/paper/1711.05224/) (2017)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)
- [PhaseMax: Convex Phase Retrieval via Basis Pursuit](https://mlsanity.com/paper/1610.07531/) (2016)
- [Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming](https://mlsanity.com/paper/1310.0807/) (2013)
- [Robust Regression via Mutivariate Regression Depth](https://mlsanity.com/paper/1702.04656/) (2017)
- [Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation](https://mlsanity.com/paper/1610.04210/) (2016)
- [PhaseLift is robust to a constant fraction of arbitrary errors](https://mlsanity.com/paper/1502.04241/) (2015)

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

- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)

## Abstract (arXiv)

In this work, we study the robust phase retrieval problem where the task is to recover an unknown signal θ^* ∈ ℝd in the presence of potentially arbitrarily corrupted magnitude-only linear measurements. We propose an alternating minimization approach that incorporates an oracle solver for a non-convex optimization problem as a subroutine. Our algorithm guarantees convergence to θ^* and provides an explicit polynomial dependence of the convergence rate on the fraction of corrupted measurements. We then provide an efficient construction of the aforementioned oracle under a sparse arbitrary outliers model and offer valuable insights into the geometric properties of the loss landscape in phase retrieval with corrupted measurements. Our proposed oracle avoids the need for computationally intensive spectral initialization, using a simple gradient descent algorithm with a constant step size and random initialization instead. Additionally, our overall algorithm achieves nearly linear sample complexity, O(d , polylog(d)).