Robust Recovery of Low-Rank Matrices via Non-Convex Optimization

In the area of low-rank recovery, existing researches find that non-convex penalties might lead to better performance than convex ones such as the nuclear norm, but until now the complete convergence guarantees of algorithms for optimization with non-convex low-rank-inducing penalties are still rare. This paper is mainly motivated by this research gap. A class of low-rank-inducing penalties is introduced with characterization of their non-convexity. By properly defining the gradients of the penalty, an algorithm is proposed to solve the non-convex optimization problem. Theoretical analysis reveals that if the non-convexity of the penalty is below a threshold (which is in inverse proportion to the distance between the initialization and the low-rank matrix), the recovery error is linear in both the step size and the noise term. Numerical simulations are implemented to test the performance of the proposed algorithm and to verify the theoretical results.