Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
This work addresses robust PCA for data analysis applications, presenting an incremental improvement with a novel formulation and algorithm.
The authors formulated robust principal component analysis (RPCA) as a best pair problem for the first time and developed an accelerated proximal gradient scheme to solve it, achieving global convergence and local linear rates while outperforming baseline algorithms in numerical experiments on real and synthetic data.
The best pair problem aims to find a pair of points that minimize the distance between two disjoint sets. In this paper, we formulate the classical robust principal component analysis (RPCA) as the best pair; which was not considered before. We design an accelerated proximal gradient scheme to solve it, for which we show global convergence, as well as the local linear rate. Our extensive numerical experiments on both real and synthetic data suggest that the algorithm outperforms relevant baseline algorithms in the literature.