A Unified Framework for Nonconvex Low-Rank plus Sparse Matrix Recovery
A Unified Framework for Nonconvex Low-Rank plus Sparse Matrix Recovery
复制标题
DOI：
--
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Xiao Zhang;Lingxiao Wang;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Xiao Zhang;Lingxiao Wang;Quanquan Gu
基于矩阵分解，我们提出了一个解决一般低秩加稀疏矩阵恢复问题的统一框架，它涵盖了满足约束强凸性和光滑性条件的广泛的目标函数族。基于投影梯度下降和双阈值算子，我们提出的通用算法在满足最好的稳健性保证(即对稀疏的容忍度)的同时，保证以局部线性速率收敛到未知的低秩稀疏矩阵。我们的理论的核心是一个新的低秩加稀疏矩阵的结构Lipschitz梯度条件，它对于证明算法的线性收敛速度是必不可少的，我们认为证明一般叠加结构模型的快速收敛速度是独立的。我们通过两个具体的例子来说明我们的框架的应用：稳健的矩阵感知和稳健的主成分分析。实证实验证实了我们的理论。
We propose a unified framework to solve general low-rank plus sparse matrix recovery problems based on matrix factorization, which covers a broad family of objective functions satisfying the restricted strong convexity and smoothness conditions. Based on projected gradient descent and the double thresholding operator, our proposed generic algorithm is guaranteed to converge to the unknown low-rank and sparse matrices at a locally linear rate, while matching the bestknown robustness guarantee (i.e., tolerance for sparsity). At the core of our theory is a novel structural Lipschitz gradient condition for low-rank plus sparse matrices, which is essential for proving the linear convergence rate of our algorithm, and we believe is of independent interest to prove fast rates for general superposition-structured models. We illustrate the application of our framework through two concrete examples: robust matrix sensing and robust PCA. Empirical experiments corroborate our theory.