Optimization Online


Rank-Sparsity Incoherence for Matrix Decomposition

Venkat Chandrasekaran (venkatc***at***mit.edu)
Sujay Sanghavi (sanghavi***at***ecn.purdue.edu)
Pablo A. Parrilo (parrilo***at***mit.edu)
Alan S. Willsky (willsky***at***mit.edu)

Abstract: 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 NP-hard 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 $\ell_1$ norm and the nuclear norm of the components. We develop a notion of \emph{rank-sparsity incoherence}, expressed as an uncertainty principle between the sparsity pattern of a matrix and its row and column spaces, and 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.

Keywords: matrix decomposition, convex relaxation, L1 norm minimization, nuclear norm minimization, uncertainty principle, semidefinite programming, rank, sparsity

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering (Control Applications )

Category 3: Applications -- Science and Engineering (Statistics )


Download: [PDF]

Entry Submitted: 06/11/2009
Entry Accepted: 06/11/2009
Entry Last Modified: 06/11/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society