Strongly convex programming for exact matrix completion and robust principal component analysis

Abstract

The common task in matrix completion (MC) and robustprinciple component analysis (RPCA) is to recover a low-rank matrixfrom a given data matrix. These problems gained great attention from various areasin applied sciences recently, especially after the publication of the pioneeringworks of Candès et al.. One fundamental result in MC and RPCA isthat nuclear norm based convex optimizations lead to the exact low-rank matrixrecovery under suitable conditions. In this paper, we extend this result by showing that strongly convex optimizations can guaranteethe exact low-rank matrix recovery as well. The result in this paper not onlyprovides sufficient conditions under which the strongly convex models lead to the exact low-rank matrix recovery,but also guides us on how to choose suitable parameters in practical algorithms.