Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery

Abstract

We study the robust recovery of a low-rank matrix from sparsely and grossly corrupted Gaussian measurements, with no prior knowledge on the intrinsic rank. We consider the robust matrix factorization approach. We employ a robust ${\ell }_1$ loss function and deal with the challenge of the unknown rank by using an overspecified factored representation of the matrix variable. We then solve the associated nonconvex nonsmooth problem using a subgradient method with diminishing stepsizes. We show that under a regularity condition on the sensing matrices and corruption, which we call restricted direction preserving property (RDPP), even with rank overspecified, the subgradient method converges to the exact low-rank solution at a sublinear rate. Moreover, our result is more general in the sense that it automatically speeds up to a linear rate once the factor rank matches the unknown rank. On the other hand, we show that the RDPP condition holds under generic settings, such as Gaussian measurements under independent or adversarial sparse corruptions, where the result could be of independent interest. Both the exact recovery and the convergence rate of the proposed subgradient method are numerically verified in the overspecified regime. Moreover, our experiment further shows that our particular design of diminishing stepsize effectively prevents overfitting for robust recovery under overparameterized models, such as robust matrix sensing and learning robust deep image prior. This regularization effect is worth further investigation.

arXiv comment75 pages, 3 figures

References in corpus (12)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Global Optimality in Low-rank Matrix Optimization
• Robust and Efficient High-dimensional Quantum State Tomography
• Denoising and Regularization via Exploiting the Structural Bias of Convolutional Generators
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Recovery of Future Data via Convolution Nuclear Norm Minimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• On the computational and statistical complexity of over-parameterized matrix sensing
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery