Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix

摘要: This paper studies algorithms for solving the problem of recovering a low-rank matrix with fraction its entries arbitrarily corrupted. can be viewed as robust version classical PCA, and arises in number application domains, including image processing, web data ranking, bioinformatic analysis. It was recently shown that under surprisingly broad conditions, it exactly solved via convex programming surrogate combines nuclear norm minimization `1-norm minimization. develops compares two complementary approaches this program. The first is an accelerated proximal gradient algorithm directly applied to primal; while second dual problem. Both are several orders magnitude faster than previous state-of-the-art problem, which based on iterative thresholding. Simulations demonstrate performance improvement obtained these algorithms, clarify their relative merits.