Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2009 | Submitted + Published
Book Section - Chapter Open

Sparse and low-rank matrix decompositions


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.

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.

Attached Files

Published - 05394889.pdf

Submitted - cspw_slr_sysid09.pdf


Files (393.5 kB)
Name Size Download all
210.5 kB Preview Download
183.0 kB Preview Download

Additional details

August 18, 2023
October 19, 2023