Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
arXiv:1709.08114
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 {\em 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.
arXiv comment30 pages, 3 figures
References in corpus (15)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- An overview of low-rank matrix recovery from incomplete observations
- Global Optimality of Local Search for Low Rank Matrix Recovery
- How to Escape Saddle Points Efficiently
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
- Matrix Completion has No Spurious Local Minimum
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
- Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
- Fast computation of the median by successive binning
- Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
- Nearly-optimal Robust Matrix Completion
- Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
- A Unified Framework for Low-Rank plus Sparse Matrix Recovery