A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion

Low-rank matrix completion recovers incomplete matrix using low-rank assumptions, which is popularly used in many applications. A recent trend is to use nonconvex regularizers that adaptively penalize singular values. They offer good recovery performance and have nice theoretical properties, but are computationally expensive due to repeated access to individual singular values. In this paper, based on the key insight that adaptive shrinkage on singular values improve empirical performance, we propose a new nonconvex low-rank regularizer called "nuclear norm minus Frobenius norm" regularizer, which is scalable, adaptive and sound. We first show it provably holds the adaptive shrinkage property. Further, we discover its factored form which bypasses the computation of singular values and allows fast optimization by general optimization algorithms. Stable recovery and convergence are guaranteed. Extensive experiments on both synthetic and real-world data sets show that the proposed method obtains state-of-the-art performance while being the fastest in comparison to existing methods.