Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 59, Issue 7, Pages 4324-4337Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2013.2249572
Keywords
Low-rank; matrix decomposition; robustness; sparsity; statistical learning
Funding
- National Science Foundation (NSF) [EFRI-0735905, EECS-1056028]
- Defense Threat Reduction Agency [HDTRA 1-08-002]
- NSF [0954059, 1017525]
- Directorate For Engineering
- Div Of Electrical, Commun & Cyber Sys [1056028] Funding Source: National Science Foundation
- Division Of Computer and Network Systems
- Direct For Computer & Info Scie & Enginr [0954059] Funding Source: National Science Foundation
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [1017525] Funding Source: National Science Foundation
Ask authors/readers for more resources
This paper considers the recovery of a low-rank matrix from an observed version that simultaneously contains both 1) erasures, most entries are not observed, and 2) errors, values at a constant fraction of (unknown) locations are arbitrarily corrupted. We provide a new unified performance guarantee on when minimizing nuclear norm plus norm succeeds in exact recovery. Our result allows for the simultaneous presence of random and deterministic components in both the error and erasure patterns. By specializing this one single result in different ways, we recover (up to poly-log factors) as corollaries all the existing results in exact matrix completion, and exact sparse and low-rank matrix decomposition. Our unified result also provides the first guarantees for 1) recovery when we observe a vanishing fraction of entries of a corrupted matrix, and 2) deterministic matrix completion.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available