Paper Info
Title
Non-Convex Low-Rank Matrix Recovery With Arbitrary Outliers Via Median-Truncated Gradient Descent
Abstract
Recent work has demonstrated the effectiveness of gradient descent for directly recovering the factors of low-rank matrices from random linear measurements in a globally convergent manner when initialized properly. However, the performance of existing algorithms is highly sensitive in the presence of outliers that may take arbitrary values. In this paper, we propose a truncated gradient descent algorithm to improve the robustness against outliers, where the truncation is performed to rule out the contributions of samples that deviate significantly from the sample median of measurement residuals adaptively in each iteration. We demonstrate that, when initialized in a basin of attraction close to the ground truth, the proposed algorithm converges to the ground truth at a linear rate for the Gaussian measurement model with a near-optimal number of measurements, even when a constant fraction of the measurements are arbitrarily corrupted. In addition, we propose a new truncated spectral method that ensures an initialization in the basin of attraction at slightly higher requirements. We finally provide numerical experiments to validate the superior performance of the proposed approach.
Year
DOI
Venue
2017
10.1093/imaiai/iaz009
INFORMATION AND INFERENCE-A JOURNAL OF THE IMA
Keywords
Field
DocType
median-truncated gradient descent, low-rank matrix recovery, non-convex approach, robust algorithms, outliers
Gradient method,Truncation,Gradient descent,Stochastic gradient descent,Mathematical optimization,Matrix (mathematics),Outlier,Low-rank approximation,Initialization,Mathematics
Journal
Volume
Issue
ISSN
9
2
2049-8764
Citations 
PageRank 
References 
1
0.35
21
Authors
4
Name
Order
Citations
PageRank
Yuanxin Li172.15
Yuejie Chi272056.67
Huishuai Zhang33412.56
Yingbin Liang41646147.64