CaltechAUTHORS
  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 . http://resolver.caltech.edu/CaltechAUTHORS:20121008-082643123

[img]
Preview
PDF - Published Version
See Usage Policy.

205Kb
[img]
Preview
PDF - Submitted Version
See Usage Policy.

178Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20121008-082643123

Abstract

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:
URLURL TypeDescription
http://dx.doi.org/10.1109/ALLERTON.2009.5394889 DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5394889PublisherUNSPECIFIED
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.
Funders:
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:http://resolver.caltech.edu/CaltechAUTHORS:20121008-082643123
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5394889&isnumber=5394483
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34735
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 16:51
Last Modified:27 Dec 2012 02:49

Repository Staff Only: item control page