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

Santanu Das, Jatin Batra · 2026

Read Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity by Santanu Das, Jatin Batra (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18245.txt.

Introduction

Santanu Das and Jatin Batra tackle phase retrieval when the data are dirty in two ways at once. Their 2026 preprint studies recovery of a signal from phaseless measurements. Each measurement keeps only the squared size of an inner product, plus noise. The noise here has heavy tails, so wild values are common. An adversary may also corrupt part of the data. The authors give a tractable method with near-linear sample complexity, meaning the needed measurements grow almost in step with the signal size.

Phase retrieval sits inside imaging, optics, and signal tools. Robust versions matter wherever sensors misbehave or foes interfere. A method that stays fast under attack is a strong result.

Catalog record

CREATORSantanu Das, Jatin Batra
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE129 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18245

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity Santanu Das, Jatin Batra Abstract Phase retrieval is the classical problem of recovering a signal x ∗ ∈ ℝ n x^{*}\in\mathbb{R}^{n} from its noisy phaseless measurements y i = ⟨ a i , x ∗ ⟩ 2 + ζ i y_{i}=\langle a_{i},x^{*}\rangle^{2}+\zeta_{i} (where ζ i \zeta_{i} denotes noise, and a i a_{i} is the sensing vector) for i ∈ [ m ] i\in[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 y i y_{i} and the sensing vectors a i a_{i} 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 ) 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 n ) sample complexity. 1 Introduction Phase retrieval. Phase retrieval is the problem of recovering a signal from phase-less measurements. In its simplest setting, the goal is to recover x^{*}\in\mathbb{R}^{n} (up to a global sign i.e. output x minimizing dist(x,x^{*}):=\min(\|x-x^{*}\|,\|x+x^{*}\| ) from (squared) magnitudes of linear measurements y_{i}=|\langle a_{i},x^{*}\rangle|^{2}+\zeta_{i},\quad\forall i=1,2\ldots,m (1) where y_{i} and a_{i} are known, and \zeta_{i} denotes noise. Broadly, phase retrieval arises in inverse problems where phase (or sign) cannot be measured, which appears in many areas like optics [ 60 ] , X-ray crystallography [ 33 , 49 ] , microscopy [ 48 ] , astronomy [ 26 ] , diffraction and array imaging [ 8 ] , acoustics [ 3 ] , blind channel estimation in wireless communications [ 55 ] , interferometry [ 17 ] , quantum mechanics [ 15 ] and quantum information [ 34 ] , heteroscedastic regression [ 16 ] etc. History of phase retrieval. While algorithms for phase retrieval in practice had been devised since the alternating minimization algorithm of Gerchberg-Saxton [ 30 , 27 , 28 , 35 , 29 ] , the problem of phase retrieval resisted provable algorithms until recently when a variety of provable techniques emerged such as spectral initialization followed by alternating minimization [ 50 , 59 ] or Wirtinger flow [ 12 , 31 , 10 , 64 ] ; and semi-definite programming [ 9 ] (for more details, see Appendix A and also the book [ 6 ] ). Measurement error model. In this work, we study the measurement error model where the noise \zeta_{i} is heavy-tailed and homoscedastic (for the formal definition, see 1.2 ) and further an \epsilon -fraction of the measurements may be adversarially corrupted (in particular, they can depend arbitrarily on all of sensing vectors a_{i} and responses y_{i} for i\in[m] ) where \epsilon>0 is known; for the formal definition, see 1.1 and 1.2 . Recently, the model of strong adversarial corruption has received a lot of attention in algorithmic robust statistics, see e.g. recent breakthroughs described in the book [ 20 ] . The following is the notion of strong adversarial corruption in robust statistics [ 18 , 44 , 21 ] : Model 1.1 . (Strong adversarial corruption) . A clean dataset (a_{i},y_{i})^{m}_{i=1} is first generated according to ( 1 ) and then the dataset is revealed to an adversary, who can inspect all m samples and arbitrarily modify an \epsilon -fraction of them. That is, the adversary is allowed to choose any subset of at most \epsilon m samples and replace both the covariates a_{i} and responses y_{i} in any manner. The learner only has access to the corrupted dataset provided by the adversary. This error model for phase retrieval was very recently studied by Buna and Rebeschini (for heavy-tailed \zeta ) [ 7 ] and Dong et al. [ 23 ] (for \zeta=0 ). Formally, for the setting of phase retrieval, in this paper, we study the following measurement models: Model 1.2 . (Gaussian phase retrieval with zero mean heavy tailed noise and strong adversarial corruption:) Measurements y_{i} are generated from an unknown x^{*}\in\mathbb{R}^{n} according to ( 1 ) with sensing vectors a_{i}\sim\mathcal{N}(0,I_{n}) 1 1 1 The Gaussian model has been the prototypical setting for algorithms for phase retrieval with provable guarantees [ 9 , 10 , 31 , 7 , 50 , 16 , 57 , 61 ] . , where \zeta_{i} is zero-mean conditioned on a_{i} i.e. \mathbb{E}[\zeta_{i}|a_{i}]=0 and homoscedastic i.e. its conditional fourth moment \mathbb{E}[\zeta^{4}|a_{i}] and its conditional variance \mathbb{E}[\zeta^{2}|a_{i}] are constants (resp. K^{4}_{4} and \sigma^{2} ) independent of a_{i} 2 2 2 This assumption on the second and the fourth moment are standard in robust statistics, see e.g. [ 7 , 51 , 52 ] . . An \epsilon -fraction of \{(a_{i},y_{i})\}^{m}_{i=1} (where both a_{i} and y_{i} can be corrupted) are then corrupted by a strong adversary as in 1.1 . 3 3 3 As stated, the m measurements are given at once to the algorithm. However, for simplicity, we will allow our algorithms to collect a constant number of times a fresh batch of m samples as in 1.2 , where the constant can depend on the error guarantees. This is also the assumption in prior robust iterative algorithms, e.g. [ 7 , 53 , 47 ] . Model 1.3 . (Gaussian phase retrieval with non-zero mean heavy-tailed noise and strong adversarial corruption). We consider the same setting as in 1.2 , with the modification that the noise has a nonzero conditional mean, i.e., \mathbb{E}[\zeta_{i}\mid a_{i}]=\mu\neq 0. Also note that \mu is unknown. Gaussian linear measurements for phase retrieval. Gaussian measurements form the canonical and most extensively studied setting in the phase retrieval literature. Many influential methods - such as Truncated Wirtinger Flow—are analyzed in this model, and several applications (including certain heteroscedastic regression [ 16 ] setups) naturally lead to Gaussian designs. Historically, theoretical advances in phase retrieval first emerged under Gaussian measurements and only later were extended to more structured models (e.g., coded diffraction patterns (CDP) [ 12 ] ), by building on insights developed in the Gaussian case. In this article, we focus exclusively on the Gaussian measurement model and leave extensions to other sensing designs, such as coded diffraction patterns, for future work. Prior work on phase retrieval with adversarial corruptions and heavy-tailed noise: There is a long line of research on phase

Read the complete text