Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
arXiv:2102.02969
Abstract
Restricted isometry property (RIP), essentially stating that the linear measurements are approximately norm-preserving, plays a crucial role in studying low-rank matrix recovery problem. However, RIP fails in the robust setting, when a subset of the measurements are grossly corrupted with noise. In this work, we propose a robust restricted isometry property, called Sign-RIP, and show its broad applications in robust low-rank matrix recovery. In particular, we show that Sign-RIP can guarantee the uniform convergence of the subdifferentials of the robust matrix recovery with nonsmooth loss function, even at the presence of arbitrarily dense and arbitrarily large outliers. Based on Sign-RIP, we characterize the location of the critical points in the robust rank-1 matrix recovery, and prove that they are either close to the true solution, or have small norm. Moreover, in the over-parameterized regime, where the rank of the true solution is over-estimated, we show that subgradient method converges to the true solution at a (nearly) dimension-free rate. Finally, we show that sign-RIP enjoys almost the same complexity as its classical counterparts, but provides significantly better robustness against noise.
References in corpus (14)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Understanding deep learning requires rethinking generalization
- Global Optimality of Local Search for Low Rank Matrix Recovery
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Matrix Completion has No Spurious Local Minimum
- Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
- Fast Algorithms for Robust PCA via Gradient Descent
- Subgradient Descent Learns Orthogonal Dictionaries
- Distillation Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
- A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization
- Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
- Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
- Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
- On the computational and statistical complexity of over-parameterized matrix sensing