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

Abstract

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.

References in corpus (10)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• Rank-Sparsity Incoherence for Matrix Decomposition
• Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset
• Fast Algorithms for Robust PCA via Gradient Descent
• Non-convex Robust PCA
• Local Linear Convergence of Forward-Backward under Partial Smoothness
• Matrix Completion under Interval Uncertainty
• A Multi-step Inertial Forward--Backward Splitting Method for Non-convex Optimization
• Weighted Low-Rank Approximation of Matrices and Background Modeling

Cited by in corpus (2)

• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters