Please use this identifier to cite or link to this item:
Title: Robust PCA via outlier pursuit
Authors: Xu, H. 
Caramanis, C.
Sanghavi, S.
Issue Date: May-2012
Citation: Xu, H., Caramanis, C., Sanghavi, S. (2012-05). Robust PCA via outlier pursuit. IEEE Transactions on Information Theory 58 (5) : 3047-3064. ScholarBank@NUS Repository.
Abstract: Singular-value decomposition (SVD) [and principal component analysis (PCA)] is one of the most widely used techniques for dimensionality reduction: successful and efficiently computable, it is nevertheless plagued by a well-known, well-documented sensitivity to outliers. Recent work has considered the setting where each point has a few arbitrarily corrupted components. Yet, in applications of SVD or PCA, such as robust collaborative filtering or bioinformatics, malicious agents, defective genes, or simply corrupted or contaminated experiments may effectively yield entire points that are completely corrupted. We present an efficient convex optimization-based algorithm that we call outlier pursuit, which under some mild assumptions on the uncorrupted points (satisfied, e.g., by the standard generative assumption in PCA problems) recovers the exact optimal low-dimensional subspace and identifies the corrupted points. Such identification of corrupted points that do not conform to the low-dimensional approximation is of paramount interest in bioinformatics, financial applications, and beyond. Our techniques involve matrix decomposition using nuclear norm minimization; however, our results, setup, and approach necessarily differ considerably from the existing line of work in matrix completion and matrix decomposition, since we develop an approach to recover the correct column space of the uncorrupted matrix, rather than the exact matrix itself. In any problem where one seeks to recover a structure rather than the exact initial matrices, techniques developed thus far relying on certificates of optimality will fail. We present an important extension of these methods, which allows the treatment of such problems. © 2011 IEEE.
Source Title: IEEE Transactions on Information Theory
ISSN: 00189448
DOI: 10.1109/TIT.2011.2173156
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 20, 2018


checked on Nov 7, 2018

Page view(s)

checked on Nov 3, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.