AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Robust Principal Component Analysis with Non-Greedy ℓ1-Norm Maximization
Feiping Nie, Heng Huang, Chris Ding, Dijun Luo, Hua Wang

Last modified: 2011-06-28

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.

Full Text: PDF