RECOVERING LOW-RANK AND SPARSE COMPONENTS OF MATRICES FROM INCOMPLETE AND NOISY OBSERVATIONS
RECOVERING LOW-RANK AND SPARSE COMPONENTS OF MATRICES FROM INCOMPLETE AND NOISY OBSERVATIONS
复制标题
从不完整和有噪声的观测中恢复矩阵的低秩和稀疏分量
DOI：
10.1137/100781894
复制
发表时间：
2011-01-01
影响因子：
3.1
通讯作者：
Yuan, Xiaoming
中科院分区：
文献类型：
--
作者：
Tao, Min;Yuan, Xiaoming
许多问题的特征是恢复给定矩阵的低级别和稀疏组件的任务。最近，发现这种非确定的多项式时间硬（NP-HARD）的任务可以通过理论上和数值来很好地完成，这是通过启发式解决凸的放松问题，在该问题中，可以利用广泛的核定标准和L（1）规范。诱导低级和稀疏性。本文研究了一般环境中的恢复任务，即只能观察到矩阵的一小部分条目，并且脉冲和高斯噪声都会损坏观察结果。我们表明，所得模型属于经典增强拉格朗日方法的适用范围。此外，新模型的可分离结构使我们能够通过拆分增强的拉格朗日函数来更有效地解决所涉及的子问题。因此，开发了一些用于求解新恢复模型的数字算法。一些初步的数值实验验证了这些基于拉格朗日的扩展算法很容易实现，并且在解决新的恢复模型方面非常有效。
Many problems can be characterized by the task of recovering the low-rank and sparse components of a given matrix. Recently, it was discovered that this nondeterministic polynomial-time hard (NP-hard) task can be well accomplished, both theoretically and numerically, via heuristically solving a convex relaxation problem where the widely acknowledged nuclear norm and l(1) norm are utilized to induce low-rank and sparsity. This paper studies the recovery task in the general settings that only a fraction of entries of the matrix can be observed and the observation is corrupted by both impulsive and Gaussian noise. We show that the resulting model falls into the applicable scope of the classical augmented Lagrangian method. Moreover, the separable structure of the new model enables us to solve the involved subproblems more efficiently by splitting the augmented Lagrangian function. Hence, some splitting numerical algorithms are developed for solving the new recovery model. Some preliminary numerical experiments verify that these augmented-Lagrangian-based splitting algorithms are easily implementable and surprisingly efficient for tackling the new recovery model.