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.

该研究提出了一个基于Frank-Wolfe和近端方法的算法，以（基本上）线性的迭代成本来解决矩阵从压缩和严重损坏的观测中恢复的问题，证明其可行性，讨论了收敛结果和实现细节，并在可视数据上进行了良好的数值实验。

可扩展的鲁棒矩阵恢复：Frank-Wolfe遇上Proximal方法