A fast factorization-based approach to robust PCA

Chong Peng, Zhao Kang, Qiang Cheng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

Robust principal component analysis (RPCA) has been widely used for recovering low-rank matrices in many data mining and machine learning problems. It separates a data matrix into a low-rank part and a sparse part. The convex approach has been well studied in the literature. However, state-of-The-Art algorithms for the convex approach usually liave relatively high complexity due to the need of solving (partial) singular value decompositions of large matrices. A non-convex approach, AltProj, has also been proposed with lighter complexity and better scalability. Given the true rank r of the underlying low rank matrix, AltProj has a complexity of 0(r2</n), where dxn is the size of data matrix. In this paper, we propose a novel factorisation-based model of RPCA, which has a complexity of O(kdn), where k is an upper bound of the true rank. Our method does not need the precise value of the true rank. From extensive experiments, we observe that AltProj cau work only when r is precisely known in advance; however, when the needed rank parameter r is specified to a value different from the true rank, AltProj cannot fully separate the two parts while our method succeeds. Even when both work, our method is about 4 times faster than AltProj. Our method can be used as a light-weight, scalable tool for RPCA in the absence of the precise value of the true rank.

Original languageEnglish
Title of host publicationProceedings - 16th IEEE International Conference on Data Mining, ICDM 2016
EditorsFrancesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu
Pages1137-1142
Number of pages6
ISBN (Electronic)9781509054725
DOIs
StatePublished - Jul 2 2016
Event16th IEEE International Conference on Data Mining, ICDM 2016 - Barcelona, Catalonia, Spain
Duration: Dec 12 2016Dec 15 2016

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
Volume0
ISSN (Print)1550-4786

Conference

Conference16th IEEE International Conference on Data Mining, ICDM 2016
Country/TerritorySpain
CityBarcelona, Catalonia
Period12/12/1612/15/16

Bibliographical note

Funding Information:
Qiang Cheng is the corresponding author. This work is supported by National Science Foundation under grant IIS- 1218712, National Natural Science Foundation of China, under grant 11241005, and Shanxi Scholarship Council of China 2015-093.

Publisher Copyright:
© 2016 IEEE.

Keywords

  • Factorization
  • Non-convex
  • Robust principal component analysis
  • Scalable

ASJC Scopus subject areas

  • Engineering (all)

Fingerprint

Dive into the research topics of 'A fast factorization-based approach to robust PCA'. Together they form a unique fingerprint.

Cite this