# Scalable Robust Matrix Recovery: Frank-Wolfe Meets Proximal Methods

arXiv: https://arxiv.org/abs/1403.7588 · HTML: https://mlsanity.com/paper/1403.7588/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2014.

## Built on by (most cited first, 7 of 7)

- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties](https://mlsanity.com/paper/2208.03622/) (2022)
- [Convex optimization over a probability simplex](https://mlsanity.com/paper/2305.09046/) (2023)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)

## Abstract (arXiv)

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.