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 language | English (US) |
---|---|
Title of host publication | 33rd International Conference on Machine Learning, ICML 2016 |
Publisher | International Machine Learning Society (IMLS) |
Pages | 1607-1627 |
Number of pages | 21 |
Volume | 3 |
ISBN (Electronic) | 9781510829008 |
State | Published - 2016 |
Event | 33rd International Conference on Machine Learning, ICML 2016 - New York City, United States Duration: Jun 19 2016 → Jun 24 2016 |
Other
Other | 33rd International Conference on Machine Learning, ICML 2016 |
---|---|
Country/Territory | United States |
City | New York City |
Period | 6/19/16 → 6/24/16 |
ASJC Scopus subject areas
- Artificial Intelligence
- Software
- Computer Networks and Communications