Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods

Abstract

Recovering matrices from compressive and grossly corrupted observations is a fundamental problem in robust statistics, with rich applications in computer vision and machine learning. In theory, under certain conditions, this problem can be solved in polynomial time via a natural convex relaxation, known as Compressive Principal Component Pursuit (CPCP). However, all existing provable algorithms for CPCP suffer from superlinear per-iteration cost, which severely limits their applicability to large scale problems. In this paper, we propose provable, scalable and efficient methods to solve CPCP with (essentially) linear per-iteration cost. Our method combines classical ideas from Frank-Wolfe and proximal methods. In each iteration, we mainly exploit Frank-Wolfe to update the low-rank component with rank-one SVD and exploit the proximal step for the sparse term. Convergence results and implementation details are also discussed. We demonstrate the scalability of the proposed approach with promising numerical experiments on visual data.

References in corpus (1)

• Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization

Cited by in corpus (15)

• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• Curvature of Feasible Sets in Offline and Online Optimization
• Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
• Fast Multilevel Algorithms for Compressive Principle Component Pursuit
• Safe Screening for the Generalized Conditional Gradient Method
• Unique sparse decomposition of low rank matrices
• Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• Outliers Detection in Networks with Missing Links
• Accelerated Affine-Invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-Loop Step-Sizes
• Semi-Stochastic Frank-Wolfe Algorithms with Away-Steps for Block-Coordinate Structure Problems
• Applications of gauge duality in robust principal component analysis and semidefinite programming
• A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming