Provable Non-convex Phase Retrieval with Outliers - Median Truncated Wirtinger Flow

Aug 26, 2026

Uploaded by Callum

Solving quadratic systems is a key task in machine learning and signal processing, with phase retrieval aiming to recover a signal from only the magnitudes of linear measurements. When measurements contain arbitrary outliers, existing non-convex gradient-descent schemes like Wirtinger flow and truncated Wirtinger flow can fail. The proposed median-truncated Wirtinger flow leverages the sample median to resist outliers in initialization and every gradient update. Theoretical guarantees show recovery with near-optimal measurement counts under Gaussian sensing, and robustness extends to bounded noise alongside arbitrary outliers, supported by new median-based concentration analysis and numerical experiments.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

AccessFree to download

Abstract

1. Introduction

1.1 Main Contributions

Provable Non-convex Phase Retrieval with Outliers: Median Truncated Wirtinger Flow Huishuai Zhang HZHAN 23@ SYR . EDU Department of EECS, Syracuse University, Syracuse, NY 13244 USA Yuejie Chi CHI.97@ OSU . EDU Department of ECE, The Ohio State University, Columbus, OH 43210 USA Yingbin Liang YLIANG06@ SYR . EDU Department of EECS, Syracuse University, Syracuse, NY 13244 USA Abstract Solving systems of quadratic equations is a central problem in machine learning and signal processing. One important example is phase retrieval, which aims to recover a signal from only magnitudes of its linear measurements. This paper focuses on the situation when the measurements are corrupted by arbitrary outliers, for which the recently developed non-convex gradient descent Wirtinger ﬂow (WF) and truncated Wirtinger ﬂow (TWF) algorithms likely fail. We develop a novel median-TWF algorithm that exploits robustness of sample median to resist arbitrary outliers in the initialization and the gradient update in each iteration. We show that such anon-convex algorithm provably recovers the signal from a near-optimal number of measurements composed of i.i.d. Gaussian entries, up to a logarithmic factor, even when a constant portion of the measurements are corrupted by arbitrary outliers. We further show that median-TWF is also robust when measurements are corrupted by both arbitrary outliers and bounded noise. Our analysis of performance guarantee is accomplished by development of non-trivial concentration measures of median-related quantities, which may be of independent interest. We further provide numerical experiments to demonstrate the effectiveness of the approach. 1. Introduction Phase retrieval is a classical problem in machine learning, signal processing and optical imaging, where one aims to Proceedings of the 33 rd International Conference on Machine Learning, New York, NY, USA, 2016 . JMLR: W&CP volume 48. Copyright 2016 by the author(s) . recover a signal x 2 Rn from only observing the magnitudes of its linear measurements: yi = j hai ; xij2 ; i = 1 ; : : : ; m: It has many important applications such as X-ray crystallography (Drenth, 2007), but is known to be notoriously difﬁcult due to the quadratic form of the measurements. Classical methods based on alternating minimization between the signal of interest and the phase information (Fienup, 1982), though computationally simple, are often trapped at local minima and lack rigorous performance guarantees. Using the lifting trick, the phase retrieval problem can be reformulated as estimating a rank-one positive semideﬁnite matrix X = xxT from linear measurements (Balan et al., 2006), to which convex relaxations into semideﬁnite programming are considered (Waldspurger et al., 2015 ; Candès et al., 2013 ; Chen et al., 2015 ; Demanet & Hand, 2014 ; Candès & Li, 2014 ; Li & Voroninski, 2013) . In particular, when the measurement vectors ai 's are composed of i.i.d. Gaussian entries, Phaselift (Candès et al., 2013) perfectly recovers all x 2 Rn with high probability as long as the number m of measurements is on the order of n. However, the computational cost of Phaselift becomes prohibitive when the signal dimension is large. Appealingly, a so-called Wirtinger ﬂow (WF) algorithm based on gradient descent was recently proposed in (Candès et al., 2015 ; Soltanolkotabi, 2014) and shown to work remarkably well: it converges to the global optima when properly initialized using the spectral method. The truncated Wirtinger ﬂow (TWF) algorithm (Chen & Candès, 2015) further improves WF by eliminating samples whose contributions to both the initialization and the search direction are excessively deviated from the sample mean, so that the behavior of each gradient update is well controlled. TWF is shown to converge globally at a geometric rate as long as m is on the order of n for i.i.d. Gaussian measurement vectors using a constant step size. Both WF and TWF algorithms have

FAQs

What problem does this paper address in phase retrieval?

It addresses phase retrieval when the magnitude measurements are corrupted by arbitrary outliers, where standard Wirtinger flow and truncated Wirtinger flow may fail.

What is the key idea behind the proposed median-TWF method?

It replaces the sample mean used in truncated Wirtinger flow with a robust sample median in both initialization and the gradient update truncation rule.

What theoretical recovery guarantees are provided?

The analysis shows provable recovery from near-optimal numbers of Gaussian measurements, up to a logarithmic factor, even when a constant portion of measurements are arbitrary outliers.

Does the method handle noise in addition to outliers?

Yes. The paper shows median-TWF is also robust when measurements include both arbitrary outliers and bounded noise, supported by new concentration results and experiments.

Aug 26, 2026

Uploaded by Callum