Nonconvex Robust Low-rank Matrix Recovery

Abstract

In this paper we study the problem of recovering a low-rank matrix from a number of random linear measurements that are corrupted by outliers taking arbitrary values. We consider a nonsmooth nonconvex formulation of the problem, in which we explicitly enforce the low-rank property of the solution by using a factored representation of the matrix variable and employ an ${\ell }_1$-loss function to robustify the solution against outliers. We show that even when a constant fraction (which can be up to almost half) of the measurements are arbitrarily corrupted, as long as certain measurement operators arising from the measurement model satisfy the so-called ${\ell }_1/{\ell }_2$-restricted isometry property, the ground-truth matrix can be exactly recovered from any global minimum of the resulting optimization problem. Furthermore, we show that the objective function of the optimization problem is sharp and weakly convex. Consequently, a subgradient Method (SubGM) with geometrically diminishing step sizes will converge linearly to the ground-truth matrix when suitably initialized. We demonstrate the efficacy of the SubGM for the nonconvex robust low-rank matrix recovery problem with various numerical experiments.

References in corpus (14)

• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Matrix Completion has No Spurious Local Minimum
• Global Optimality in Low-rank Matrix Optimization
• Gradient Descent Converges to Minimizers
• Non-convex Robust PCA
• The Non-convex Geometry of Low-rank Matrix Optimization
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Subgradient Descent Learns Orthogonal Dictionaries
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization
• Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit

Cited by in corpus (2)

• Subgradient Descent Learns Orthogonal Dictionaries
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint