A Caltech Library Service

Sparse and low-rank matrix decompositions

Chandrasekaran, Venkat and Sanghavi, Sujay and Parrilo, Pablo A. and Willsky, Alan S. (2009) Sparse and low-rank matrix decompositions. In: Forty-Seventh annual Allerton Conference on Communication, Control, and Computing. IEEE , Piscataway, NJ, pp. 962-967. ISBN 978-1-4244-5870-7 .

PDF - Published Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the following fundamental problem: given a matrix that is the sum of an unknown sparse matrix and an unknown low-rank matrix, is it possible to exactly recover the two components? Such a capability enables a considerable number of applications, but the goal is both ill-posed and NP-hard in general. In this paper we develop (a) a new uncertainty principle for matrices, and (b) a simple method for exact decomposition based on convex optimization. Our uncertainty principle is a quantification of the notion that a matrix cannot be sparse while having diffuse row/column spaces. It characterizes when the decomposition problem is ill-posed, and forms the basis for our decomposition method and its analysis. We provide deterministic conditions - on the sparse and low-rank components - under which our method guarantees exact recovery.

Item Type:Book Section
Related URLs:
Additional Information:© 2009 IEEE. Date of Current Version: 22 January 2010. This work was supported by MURI AFOSR grant FA9550-06-1-0324, MURI AFOSR grant FA9550-06-1-0303, and NSF FRG 0757207.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR) Multidisciplinary University Research Initiative (MURI)FA9550-06-1-0324
Air Force Office of Scientific Research (AFOSR) Multidisciplinary University Research Initiative (MURI)FA9550-06-1-0303
NSFFRG 0757207
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number11135166
Record Number:CaltechAUTHORS:20121008-082643123
Persistent URL:
Official Citation:Chandrasekaran, V.; Sanghavi, S.; Parrilo, P.A.; Willsky, A.S.; , "Sparse and low-rank matrix decompositions," Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on , vol., no., pp.962-967, Sept. 30 2009-Oct. 2 2009 doi: 10.1109/ALLERTON.2009.5394889 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34735
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 16:51
Last Modified:03 Oct 2019 04:21

Repository Staff Only: item control page