Provable non-convex phase retrieval with outliers: Median truncated Wirtinger flow

Huishuai Zhang, Yuejie Chi, Yingbin Liang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

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 flow (WF) and truncated Wirtinger flow (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 a non-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.

Original languageEnglish (US)
Title of host publication33rd International Conference on Machine Learning, ICML 2016
PublisherInternational Machine Learning Society (IMLS)
Pages1607-1627
Number of pages21
Volume3
ISBN (Electronic)9781510829008
StatePublished - 2016
Event33rd International Conference on Machine Learning, ICML 2016 - New York City, United States
Duration: Jun 19 2016Jun 24 2016

Other

Other33rd International Conference on Machine Learning, ICML 2016
CountryUnited States
CityNew York City
Period6/19/166/24/16

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Provable non-convex phase retrieval with outliers: Median truncated Wirtinger flow'. Together they form a unique fingerprint.

  • Cite this

    Zhang, H., Chi, Y., & Liang, Y. (2016). Provable non-convex phase retrieval with outliers: Median truncated Wirtinger flow. In 33rd International Conference on Machine Learning, ICML 2016 (Vol. 3, pp. 1607-1627). International Machine Learning Society (IMLS).