Pathwise component descent method with MC+ penalty for low rank matrix recovery

• A new algorithm for low rank matrix recovery.
• Our algorithm can avoid getting trapped into a bad local minimum.
• Provide convergence guarantee for the proposed algorithm.
• Numerical results on matrix completion show superiority.

We consider the low rank matrix recovery (LRM) problem, which recovers an unknown low rank matrix from very limited information. Although recent study has shown that non-convex models for LRM can serve as better approximation of low rank regularization and outperform their convex counterpart, these models suffer from getting trapped into a bad local minimum. We propose an algorithm, named PIC-LR, to address this problem. PIC-LR is inspired by a recent algorithm, called SparseNet, which addresses analogical problem in the study of sparse optimization. Specifically, we take advantage of the properties of MC+ penalty and employ path-following technique. We also generalize coordinate descent to better imitate SparseNet. In numerical experiment, we apply PIC-LR to matrix completion problem, and the results show that PIC-LR outperforms several state-of-the-art solvers in terms of precision.