Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity
We consider convex optimization problems which are widely used as convex relaxations for low-rank matrix recovery problems. In particular, in several important problems, such as phase retrieval and robust PCA, the underl…
RetrievalGridless 2D Recovery of Lines using the Sliding Frank-Wolfe Algorithm
We present a new approach leveraging the Sliding Frank--Wolfe algorithm to address the challenge of line recovery in degraded images. Building upon advances in conditional gradient methods for sparse inverse problems wit…
Line DetectionAn Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion
Motivated principally by the low-rank matrix completion problem, we present an extension of the Frank-Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. This i…
Low-Rank Matrix CompletionMatrix CompletionFrank Wolfe Meets Metric Entropy
The Frank-Wolfe algorithm has seen a resurgence in popularity due to its ability to efficiently solve constrained optimization problems in machine learning and high-dimensional statistics. As such, there is much interest…
A Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron
We consider the problem of minimizing a smooth and convex function over the $n$-dimensional spectrahedron -- the set of real symmetric $n\times n$ positive semidefinite matrices with unit trace, which underlies numerous …