Analysis of robust PCA via local incoherence

Huishuai Zhang, Yi Zhou, Yingbin Liang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

We investigate the robust PCA problem of decomposing an observed matrix into the sum of a low-rank and a sparse error matrices via convex programming Principal Component Pursuit (PCP). In contrast to previous studies that assume the support of the error matrix is generated by uniform Bernoulli sampling, we allow non-uniform sampling, i.e., entries of the low-rank matrix are corrupted by errors with unequal probabilities. We characterize conditions on error corruption of each individual entry based on the local incoherence of the low-rank matrix, under which correct matrix decomposition by PCP is guaranteed. Such a refined analysis of robust PCA captures how robust each entry of the low rank matrix combats error corruption. In order to deal with non-uniform error corruption, our technical proof introduces a new weighted norm and develops/exploits the concentration properties that such a norm satisfies.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems
PublisherNeural information processing systems foundation
Pages1819-1827
Number of pages9
Volume2015-January
StatePublished - 2015
Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
Duration: Dec 7 2015Dec 12 2015

Other

Other29th Annual Conference on Neural Information Processing Systems, NIPS 2015
CountryCanada
CityMontreal
Period12/7/1512/12/15

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint Dive into the research topics of 'Analysis of robust PCA via local incoherence'. Together they form a unique fingerprint.

  • Cite this

    Zhang, H., Zhou, Y., & Liang, Y. (2015). Analysis of robust PCA via local incoherence. In Advances in Neural Information Processing Systems (Vol. 2015-January, pp. 1819-1827). Neural information processing systems foundation.