Linear time Principal Component Pursuit and its extensions using l(1)   filtering

doi:10.1016/j.neucom.2014.03.046

CORC > 北京大学 > 信息科学技术学院

	Linear time Principal Component Pursuit and its extensions using l(1) filtering
	Liu, Risheng ; Lin, Zhouchen ; Su, Zhixun ; Gao, Junbin
刊名	neurocomputing
	2014
关键词	Robust principal component analysis Principal component Pursuit l(1) minimization Subspace learning Incremental learning VISUAL TRACKING ROBUST MATRIX ALGORITHMS
DOI	10.1016/j.neucom.2014.03.046
英文摘要	In the past decades, exactly recovering the intrinsic data structure from corrupted observations, which is known as Robust Principal Component Analysis (RPCA), has attracted tremendous interests and found many applications in computer vision and pattern recognition. Recently, this problem has been formulated as recovering a low-rank component and a sparse component from the observed data matrix. It is proved that under some suitable conditions, this problem can be exactly solved by Principal Component Pursuit (PCP), i.e., minimizing a combination of nuclear norm and l(1) norm. Most of the existing methods for solving PCP require Singular Value Decompositions (SVDs) of the data matrix, resulting in a high computational complexity, hence preventing the applications of RPCA to very large scale computer vision problems. In this paper, we propose a novel algorithm, called l(1) filtering, for exactly solving PCP with an O(r(2)(m+n)) complexity, where m x n is the size of data matrix and r is the rank of the matrix to recover, which is supposed to be much smaller than m and n. Moreover, if filtering is highly parallelizable. It is the first algorithm that can exactly solve a nuclear norm minimization problem in linear time (with respect to the data size). As a preliminary investigation, we also discuss the potential extensions of PCP for more complex vision tasks encouraged by l(1) filtering. Experiments on both synthetic data and real tasks testify the great advantage of l(1) filtering in speed over state-of-the-art algorithms and wide applications in computer vision and pattern recognition societies. (C) 2014 Elsevier B.V. All rights reserved.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000340341400055&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Artificial Intelligence; SCI(E); 10; ARTICLE; rsliu@dlut.edu.cn; zlin@pku.edu.cn; zxsu@dlut.edu.cn; jbgao@csu.edu.au; ,SI; 529-541; 142
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/209900]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Liu, Risheng,Lin, Zhouchen,Su, Zhixun,et al. Linear time Principal Component Pursuit and its extensions using l(1) filtering[J]. neurocomputing,2014.
APA	Liu, Risheng,Lin, Zhouchen,Su, Zhixun,&Gao, Junbin.(2014).Linear time Principal Component Pursuit and its extensions using l(1) filtering.neurocomputing.
MLA	Liu, Risheng,et al."Linear time Principal Component Pursuit and its extensions using l(1) filtering".neurocomputing (2014).