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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/58946 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1826205869031817216 |
|---|---|
| author | Chandrasekaran, Venkat Sanghavi, Sujay Parrilo, Pablo A. Willsky, Alan S. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Chandrasekaran, Venkat Sanghavi, Sujay Parrilo, Pablo A. Willsky, Alan S. |
| author_sort | Chandrasekaran, Venkat |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:20:43Z |
| format | Article |
| id | mit-1721.1/58946 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:20:43Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/589462022-10-01T14:38:45Z Sparse and low-rank matrix decompositions Chandrasekaran, Venkat Sanghavi, Sujay Parrilo, Pablo A. Willsky, Alan S. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Parrilo, Pablo A. Chandrasekaran, Venkat Sanghavi, Sujay Parrilo, Pablo A. Willsky, Alan S. 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. United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (grant FA9550-06-1-0324) United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (grant FA9550-06-1-0303) National Science Foundation (U.S.). Focused Research Group (0757207) 2010-10-07T17:14:23Z 2010-10-07T17:14:23Z 2010-01 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5870-7 INSPEC Accession Number: 11135166 http://hdl.handle.net/1721.1/58946 Chandrasekaran, V. et al. “Sparse and low-rank matrix decompositions.” Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on. 2009. 962-967. © 2009 IEEE https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/ALLERTON.2009.5394889 47th Annual Allerton Conference on Communication, Control, and Computing, 2009 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Chandrasekaran, Venkat Sanghavi, Sujay Parrilo, Pablo A. Willsky, Alan S. Sparse and low-rank matrix decompositions |
| title | Sparse and low-rank matrix decompositions |
| title_full | Sparse and low-rank matrix decompositions |
| title_fullStr | Sparse and low-rank matrix decompositions |
| title_full_unstemmed | Sparse and low-rank matrix decompositions |
| title_short | Sparse and low-rank matrix decompositions |
| title_sort | sparse and low rank matrix decompositions |
| url | http://hdl.handle.net/1721.1/58946 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT chandrasekaranvenkat sparseandlowrankmatrixdecompositions AT sanghavisujay sparseandlowrankmatrixdecompositions AT parrilopabloa sparseandlowrankmatrixdecompositions AT willskyalans sparseandlowrankmatrixdecompositions |