2013 RobustPrincipalComponentAnalysi

• (Sun et al., 2013) ⇒ Qian Sun, Shuo Xiang, and Jieping Ye. (2013). “Robust Principal Component Analysis via Capped Norms.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487604

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Robust+Principal+Component+Analysis+via+Capped+Norms
• http://dl.acm.org/citation.cfm?id=2487575.2487604&preflayout=flat#citedby

Quotes

Author Keywords

• Admm; database applications; dc programming; image processing; low-rank; non-convex optimization; sparsity; trace norm

Abstract

In many applications such as image and video processing, the data matrix often possesses simultaneously a low-rank structure capturing the global information and a sparse component capturing the local information. How to accurately extract the low-rank and sparse components is a major challenge. Robust Principal Component Analysis (RPCA) is a general framework to extract such structures. It is well studied that under certain assumptions, convex optimization using the trace norm and ℓ1-norm can be an effective computation surrogate of the difficult RPCA problem. However, such convex formulation is based on a strong assumption which may not hold in real-world applications, and the approximation error in these convex relaxations often cannot be neglected. In this paper, we present a novel non-convex formulation for the RPCA problem using the capped trace norm and the capped ℓ1-normm. In addition, we present two algorithms to solve the non-convex optimization: one is based on the Difference of Convex functions (DC) framework and the other attempts to solve the sub-problems via a greedy approach. Our empirical evaluations on synthetic and real-world data show that both of the proposed algorithms achieve higher accuracy than existing convex formulations. Furthermore, between the two proposed algorithms, the greedy algorithm is more efficient than the DC programming, while they achieve comparable accuracy.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 RobustPrincipalComponentAnalysi	Jieping Ye Shuo Xiang Qian Sun			Robust Principal Component Analysis via Capped Norms				10.1145/2487575.2487604		2013