Robust Principal Component Analysis with Non-Greedy l1-Norm Maximization

Nie, Feiping; Huang, Heng; Ding, Chris H. Q.; Luo, Dijun; Wang, Hua

doi:10.5591/978-1-57735-516-8/IJCAI11-242

Robust Principal Component Analysis with Non-Greedy l1-Norm Maximization

Feiping Nie, Heng Huang, Chris H. Q. Ding, Dijun Luo, Hua Wang

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1433-1437.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-242

Abstract

Principal Component Analysis (PCA) is one of the most important methods to handle high-dimensional data. However, the high computa-tional complexity makes it hard to apply to the large scale data with high dimensionality, and the used 2-norm makes it sensitive to outliers. A recent work proposed principal component analysis based on 1-norm maximization, which is efficient and robust to outliers. In that work, a greedy strategy was applied due to the difficulty of directly solving the 1-norm maximization problem, which is easy to get stuck in local solution. In this paper, we first propose an efficient optimization algorithm to solve a general 1-norm maximization problem, and then propose a robust principal component analysis with non-greedy 1-norm maximization. Experimental results on real world datasets show that the non-greedy method always obtains much better solution than that of the greedy method.

Feiping Nie, Heng Huang, Chris H. Q. Ding, Dijun Luo, and Hua Wang. 2011. Robust Principal Component Analysis with Non-Greedy l1-Norm Maximization. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1433–1437. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-242

@inproceedings{ijcai2011p242,
  title     = {Robust Principal Component Analysis with Non-Greedy l1-Norm Maximization},
  author    = {Nie, Feiping and Huang, Heng and Ding, Chris H. Q. and Luo, Dijun and Wang, Hua},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1433--1437},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-242},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-242},
}

TY  - CPAPER
TI  - Robust Principal Component Analysis with Non-Greedy l1-Norm Maximization
AU  - Nie, Feiping
AU  - Huang, Heng
AU  - Ding, Chris H. Q.
AU  - Luo, Dijun
AU  - Wang, Hua
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1433
EP  - 1437
DO  - 10.5591/978-1-57735-516-8/IJCAI11-242
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-242
ER  -