Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit

Given two disjoint sets, the best pair problem aims to find a point in one set and another point in the other set with minimal distance between them. In this paper, we formulate the classical robust principal component analysis (RPCA) problem as a best pair problem and design an accelerated proximal gradient algorithm to solve it. We prove that the method enjoys global convergence with a local linear rate. Our extensive numerical experiments on both real and synthetic data sets suggest that our proposed algorithm outperforms relevant baseline algorithms in the literature.