Robust Matrix Decomposition With Sparse Corruptions

Suppose a given observation matrix can be decomposed as the sum of a low-rank matrix and a sparse matrix, and the goal is to recover these individual components from the observed sum. Such additive decompositions have applications in a variety of numerical problems including system identification, l...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2011-11, Vol.57 (11), p.7221-7234
Main Authors: Hsu, D., Kakade, S. M., Tong Zhang
Format: Article
Language:English
Subjects:
Applied sciences
Decomposition
Detection, estimation, filtering, equalization, prediction
Exact sciences and technology
Identification
Information theory
Information, signal and communications theory
Low-rank
Matrix
Matrix decomposition
matrix decompositions
Norms
Optimization
outliers
Principal component analysis
Principal components analysis
Programming
Recovering
Recovery
Signal and communications theory
Signal, noise
Sparse matrices
sparsity
Stands
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Suppose a given observation matrix can be decomposed as the sum of a low-rank matrix and a sparse matrix, and the goal is to recover these individual components from the observed sum. Such additive decompositions have applications in a variety of numerical problems including system identification, latent variable graphical modeling, and principal components analysis. We study conditions under which recovering such a decomposition is possible via a combination of ℓ 1 norm and trace norm minimization. We are specifically interested in the question of how many sparse corruptions are allowed so that convex programming can still achieve accurate recovery, and we obtain stronger recovery guarantees than previous studies. Moreover, we do not assume that the spatial pattern of corruptions is random, which stands in contrast to related analyses under such assumptions via matrix completion.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2011.2158250