# Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 70 references that are in the map.
- First posted on arXiv 26 Jan 2026.

## Builds on (most cited first, 30 of 36)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [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)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (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)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Robust Meta-learning for Mixed Linear Regression with Small Batches](https://mlsanity.com/paper/2006.09702/) (2020)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval](https://mlsanity.com/paper/1705.02356/) (2017)
- [Phase retrieval with random Gaussian sensing vectors by alternating projections](https://mlsanity.com/paper/1609.03088/) (2016)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time](https://mlsanity.com/paper/2006.13312/) (2020)
- [Efficient learning with robust gradient descent](https://mlsanity.com/paper/1706.00182/) (2017)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent](https://mlsanity.com/paper/2105.03678/) (2021)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Median-Truncated Nonconvex Approach for Phase Retrieval with Outliers](https://mlsanity.com/paper/1603.03805/) (2016)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Near Optimal Heteroscedastic Regression with Symbiotic Learning](https://mlsanity.com/paper/2306.14288/) (2023)
- [Stable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2405.10754/) (2024)
- [Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing](https://mlsanity.com/paper/2403.10547/) (2024)
- [Robust Gradient Descent for Phase Retrieval](https://mlsanity.com/paper/2410.10623/) (2024)

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

- [Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption](https://mlsanity.com/paper/2605.29497/) (2026)

## Abstract (arXiv)

Phase retrieval is the classical problem of recovering a signal x^* ∈ ℝn from its noisy phaseless measurements yi = langle ai, x^* rangle2 + zetai (where zetai denotes noise, and ai is the sensing vector) for i ∈ [m]. The problem of phase retrieval has a rich history, with a variety of applications such as optics, crystallography, heteroscedastic regression, astrophysics, etc. A major consideration in algorithms for phase retrieval is robustness against measurement errors. In recent breakthroughs in algorithmic robust statistics, efficient algorithms have been developed for several parameter estimation tasks such as mean estimation, covariance estimation, robust principal component analysis (PCA), etc. in the presence of heavy-tailed noise and adversarial corruptions. In this paper, we study efficient algorithms for robust phase retrieval with heavy-tailed noise when a constant fraction of both the measurements yi and the sensing vectors ai may be arbitrarily adversarially corrupted. For this problem, Buna and Rebeschini (AISTATS 2025) very recently gave an exponential time algorithm with sample complexity O(n log n). Their algorithm needs a robust spectral initialization, specifically, a robust estimate of the top eigenvector of a covariance matrix, which they deemed to be beyond known efficient algorithmic techniques (similar spectral initializations are a key ingredient of a large family of phase retrieval algorithms). In this work, we make a connection between robust spectral initialization and recent algorithmic advances in robust PCA, yielding the first polynomial-time algorithms for robust phase retrieval with both heavy-tailed noise and adversarial corruptions, in fact with near-linear (in n) sample complexity.