Thumbnail
Access Restriction
Subscribed

Author Cands, Emmanuel J. ♦ Li, Xiaodong ♦ Ma, Yi ♦ Wright, John
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword $ℓ_{1}-norm$ minimization ♦ Principal components ♦ Duality ♦ Low-rank matrices ♦ Nuclear-norm minimization ♦ Robustness vis-a-vis outliers ♦ Sparsity ♦ Video surveillance
Abstract This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components $\textit{exactly}$ by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the $ℓ_{1}$ norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-06-09
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 58
Issue Number 3
Page Count 37
Starting Page 1
Ending Page 37


Open content in new tab

   Open content in new tab
Source: ACM Digital Library