RANK-SPARSITY INCOHERENCE FOR MATRIX DECOMPOSITION
RANK-SPARSITY INCOHERENCE FOR MATRIX DECOMPOSITION
复制标题
DOI：
10.1137/090761793
复制
发表时间：
2011-01-01
影响因子：
3.1
通讯作者：
Willsky, Alan S.
中科院分区：
文献类型：
--
作者：
Chandrasekaran, Venkat;Sanghavi, Sujay;Willsky, Alan S.
假设我们给定一个矩阵，该矩阵是由一个未知稀疏矩阵与一个未知低秩矩阵相加而成。我们的目标是将给定的矩阵分解成稀疏和低秩的分量。这样的问题出现在模型和系统识别中的许多应用中，并且通常难以解决。在本文中，我们考虑了一个凸优化公式，指定的矩阵分解成它的组件，通过最小化的线性组合的l（1）范数和核范数的组件。我们开发了一个概念的秩稀疏不相干，表示为矩阵的稀疏模式和它的行和列空间之间的不确定性原则，我们用它来表征基本的可识别性以及（确定性）的充分条件，精确恢复。我们的分析是几何性质的切线空间的代数品种的稀疏和低秩矩阵发挥了突出的作用。当稀疏和低秩矩阵是从某些自然随机系综，我们证明了精确恢复的充分条件满足高概率。我们得出结论与合成矩阵分解问题的模拟结果。
Suppose we are given a matrix that is formed by adding an unknown sparse matrix to an unknown low-rank matrix. Our goal is to decompose the given matrix into its sparse and low-rank components. Such a problem arises in a number of applications in model and system identification and is intractable to solve in general. In this paper we consider a convex optimization formulation to splitting the specified matrix into its components by minimizing a linear combination of the l(1) norm and the nuclear norm of the components. We develop a notion of rank-sparsity incoherence, expressed as an uncertainty principle between the sparsity pattern of a matrix and its row and column spaces, and we use it to characterize both fundamental identifiability as well as (deterministic) sufficient conditions for exact recovery. Our analysis is geometric in nature with the tangent spaces to the algebraic varieties of sparse and low-rank matrices playing a prominent role. When the sparse and low-rank matrices are drawn from certain natural random ensembles, we show that the sufficient conditions for exact recovery are satisfied with high probability. We conclude with simulation results on synthetic matrix decomposition problems.