A Caltech Library Service

Rank-Sparsity Incoherence for Matrix Decomposition

Chandrasekaran, Venkat and Sanghavi, Sujay and Parrilo, Pablo A. and Willsky, Alan S. (2011) Rank-Sparsity Incoherence for Matrix Decomposition. SIAM Journal of Optimization, 21 (2). pp. 572-596. ISSN 1052-6234.

PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 ℓ_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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2011 Society for Industrial and Applied Mathematics. Received by the editors June 11, 2009; accepted for publication (in revised form) November 8, 2010; published electronically June 30, 2011. This work was supported by MURI AFOSR grant FA9550-06-1-0324, MURI AFOSR grant FA9550-06-1-0303, and NSF FRG 0757207. A preliminary version of this work appeared in Sparse and low-rank matrix decompositions, in Proceedings of the 15th IFAC Symposium on System Identification, 2009.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0324
Air Force Office of Scientific Research (AFOSR)FA9550-06-1-0303
Subject Keywords:matrix decomposition, convex relaxation, ℓ1 norm minimization, nuclear norm minimization, uncertainty principle, semidefinite programming, rank, sparsity
Issue or Number:2
Classification Code:AMS: 90C25, 90C22, 90C59, 93B30
Record Number:CaltechAUTHORS:20121008-095909823
Persistent URL:
Official Citation:Rank-Sparsity Incoherence for Matrix Decomposition Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, and Alan S. Willsky SIAM J. Optim. 21-2 (2011), pp. 572-596
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34747
Deposited By: Ruth Sustaita
Deposited On:08 Oct 2012 17:41
Last Modified:03 Oct 2019 04:21

Repository Staff Only: item control page