RPCA最全文献和代码_RPCA原理资源-CSDN文库

共9个文件

zip：5个

pdf：4个

RPCA

5星 · 超过95%的资源需积分: 46 197 浏览量 2015-01-11 20:09:14 上传评论 41 收藏 13.47MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

RPCA.zip （9个子文件）

RPCA

nips2009.pdf 350KB

RPCA_ALM_pub.zip 10.32MB

inexact_alm_rpca.zip 372KB

LRSD-Code.zip 5KB

exact_alm_rpca.zip 372KB

Inductive Robust Principal Component Analysis.pdf 1.34MB

The Augmented Lagrange Multiplier Method.pdf 295KB

Robust Principal Component Analysis.pdf 288KB

apg_partial.zip 373KB

3794 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 8, AUGUST 2012

Correspondence

Inductive Robust Principal Component Analysis

Bing-Kun Bao, Guangcan Liu, Member, IEEE,

Changsheng Xu, Senior Member, IEEE,

and Shuicheng Yan, Senior Member, IEEE

Abstract—In this paper, we address the error correction

problem, that is, to uncover the low-dimensional subspace struc-

ture from high-dimensional observations, which are possibly

corrupted by errors. When the errors are of Gaussian distri-

bution, principal component analysis (PCA) can ﬁnd the optimal

(in terms of least-square error) low-rank approximation to high-

dimensional data. However, the canonical PCA method is known

to be extremely fragile to the presence of gross corruptions.

Recently, Wright et al. established a so-called robust principal

component analysis (RPCA) method, which can well handle the

grossly corrupted data. However, RPCA is a transductive method

and does not handle well the new samples, which are not involved

in the training procedure. Given a new datum, RPCA essentially

needs to recalculate over all the data, resulting in high computa-

tional cost. So, RPCA is inappropriate for the applications that

require fast online computation. To overcome this limitation, in

this paper, we propose an inductive robust principal component

analysis (IRPCA) method. Given a set of training data, unlike

RPCA that targets on recovering the original data matrix, IRPCA

aims at learning the underlying projection matrix, which can be

used to efﬁciently remove the possible corruptions in any datum.

The learning is done by solving a nuclear-norm regularized

minimization problem, which is convex and can be solved in

polynomial time. Extensive experiments on a benchmark human

face dataset and two video surveillance datasets show that IRPCA

cannot only be robust to gross corruptions, but also handle the

new data well and in an efﬁcient way.

Index Terms— Error correction, robust principal component

analysis (PCA), subspace learning.

I. INTRODUCTION

Data that arise from real applications, such as computer vision and

document analysis, are often characterized by low-rank subspaces,

leading to the challenging problem of exploring the low-rank sub-

space structures of the data [1]–[6]. Generally, a fundamental problem

Manuscript received May 14, 2011; revised February 21, 2012; accepted

March 10, 2012. Date of publication April 3, 2012; date of current version

July 18, 2012. This work was supported in part by the National Program

on Key Basic Research Project 973 Program under Project 2012CB316304,

the National Natural Science Foundation of China under Grant 90920303

and Grant 61003161, the China Post-Doctoral Science Foundation under

Grant 2011M500430, and the Project Grant NRF2007IDM-IDM002-069 on

Life Spaces from the IDM Project Ofﬁce, Media Development Authority,

Singapore. The associate editor coordinating the review of this manuscript

and approving it for publication was Prof. Rafael Molina.

B.-K. Bao and C. Xu are with the National Laboratory of Pattern

Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing

100190, China, and also with the China-Singapore Institute of Digital Media,

119613, Singapore (e-mail:bingkunbao@gmail.com; csxu@nlpr.ia.ac.cn).

G. Liu is with the University of Illinois at Urbana-Champaign, Urbana, IL

61801 USA (e-mail: gcliu@illinois.edu).

S. Yan is with the National University of Singapore, 10000, Singapore

(e-mail: eleyans@nus.edu.sg).

Color versions of one or more of the ﬁgures in this paper are available

online at http://ieeexplore.ieee.org.

Digital Object Identiﬁer 10.1109/TIP.2012.2192742

in this topic is to handle the data containing errors, i.e., the error

correction problem described as follows.

Problem 1 (Error Correction): Suppose the data are generated by

x = y + e, x ∈

(1)

where y lies on a subspace of low-rank and e is the error term.

Given any data vector x generated as above, the goal is to identify

the original data vector y and the error e.

Statistically, the above problem is equal to exploring the principal

components (identiﬁed by y) of the data, as a low-rank subspace can

be well modeled by a degenerate Gaussian distribution [7]. Provided

that the errors follow Gaussian distribution with small variance,

the widely used principal component analysis (PCA) [8] can well

handle the above problem. Given a set of n training data vectors

X =[x

, x

,...,x

], with each x

being generated as in (1),

PCA learns a low-rank projection by minimizing the following

reconstruction errors:

min

X − UU

X

, s.t. U

U = I

(2)

where I

is an identity matrix of size r × r, ·

denotes the

Frobenious norm of a matrix, and r is a parameter that speciﬁes

the rank of U (i.e., the number of columns of U). The solution to

the above optimization problem can be efﬁciently found by singular

value decomposition (SVD), which is computationally stable. For a

given data vector x, its principal components y can be estimated by

y = U

∗

)

x (3)

where U

∗

is learnt from a training set X by solving (2), i.e.,

calculating the SVD of X. Due to the advantages of computational

stability and efﬁciency, PCA has become one of the most widely used

tools for error correction. However, in real scenario, the application

and performance of PCA are limited due to lack of robustness to

gross corruptions, that is, the estimation obtained by PCA could be

far away from the underlying true subspace structure in the presence

of gross corruptions [9], as illustrated in Fig. 1. To overcome the

limitations of PCA, recent years have witnessed a surge of robust

principal component analysis (RPCA) methods (e.g., [9]–[15]). In

particular, Wright et al. [9], [14] recently established a RPCA method

which is emerging as a powerful tool for various applications, such

as document analysis [16], multimedia [17], and image processing

[18]. For a given set of data vectors X =[x

, x

,...,x

],RPCA

ﬁnds their principal components Y =[y

, y

,...,y

] by solving the

following convex optimization problems:

min

Y,E

Y

∗

+ λE

, s.t. X = Y + E (4)

where ·

∗

denotes the nuclear-norm, also known as the trace-norm or

Ky Fan-norm (sum of the singular values), ·

is the 

-norm chosen

for characterizing the corruptions possibly existed in data, and λ>0

is a parameter. Unlike the small Gaussian noise assumed in PCA,

RPCA can well handle the gross corruptions of large magnitude [9],

provided that the corruptions are sparse enough (i.e., only a fraction

of entries are corrupted). Note here that the sparse assumption is mild,

since it is ubiquitous in reality due to occlusion or sensor failure. It is

Notice that there are many RPCA methods in existence. For ease of

presentation, in this paper, “RPCA” solely refers to the method introduced

in [9] and [14].

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 8, AUGUST 2012 3795

true subspace

PCA

corrupted points

Fig. 1. Illustrating that PCA cannot well handle the data corrupted by gross

corruptions.

also necessary, because in unsupervised environments, the learning

is impractical if all the entries of X have been grossly corrupted.

However, it is not easy for RPCA to generalize the learnt model to

new data. Let (Y

∗

, E

∗

) be the optimal solution to (4), then a possible

way for RPCA to be used with test data is as follows: compute the

SVD of Y

∗

, denoted as Y

∗

= U

∗



∗

, and use y = U

∗

)

x to

deal with any new datum x. This approach (denoted as “RPCA_I”),

unfortunately, does not work well, as it cannot even well handle the

training data X itself. To be more precise, the produced solution

∗

)

X, X −U

∗

)

X) may be not optimal to (4). Evidence

is that the error term estimated by E = X −U

∗

)

X is usually not

sparse, as veriﬁed by our experiments. Hence, RPCA is essentially

a transductive method, which is inappropriate for the applications

requiring online computation.

Due to the limitations of PCA and RPCA, in this paper, we

therefore introduce the so-called inductive robust principal component

analysis (IRPCA), which cannot only well handle the gross corrup-

tions (comparable to RPCA), but also own good generalization ability

(much better than PCA and RPCA_I). To achieve this, we establish a

simple but effective algorithm to learn a low-rank projection from a

given set of training data. The learning is done by solving a nuclear-

norm regularized minimization problem, which is convex and can be

solved in polynomial. For any new datum corrupted by gross errors,

the learnt projection can efﬁciently remove the possible corruptions

by projecting the datum onto its underlying subspace. Extensive

experiments on a benchmark human face dataset and two video

surveillance datasets show that IRPCA cannot only be robust to gross

corruptions, but also handle well the new data in an efﬁcient way.

II. RELATED WORK

Error correction has a long history (e.g., [9]–[15]). The rather

old methods (e.g., [19] and [20]) usually suffer two pitfalls: per-

formance degradation with dimension increase and computational

intractability. To be more precise, these methods have breakdown

points proportional to the inverse of dimensionality, and hence are

useless in the high-dimensional regime we consider. Algorithms with

nondiminishing breakdown points, such as projection-pursuit [12]

are nonconvex or even combinatorial, and hence computationally

intractable (NP-hard) as the size of the problem scales.

Methods based on nuclear-norm minimization to recover

low-rank matrices are now standard (e.g., [9], [14], [15], [21],

and [22]). In particular, the work done by Wright et al. [14],

which is referred to as “RPCA” in this paper, has taken the nuclear-

norm minimization to address the error correction problem 1. While

RPCA is powerful in terms of both theory [9] and applications

[16]–[18], as discussed in Section I, it is essentially a transductive

method and is inappropriate for the applications requiring online

computation. Namely, given a new datum, RPCA essentially needs

to recalculate over all the data, resulting in high computational cost.

Recently, Liu et al. [6], [23] generalize the concept of RPCA,

and establish the so-called low-rank representation (LRR) method.

The general formulation of LRR is as follows:

min

Z,E

Z

∗

+λE



, s.t. X = AZ + E (5)

where A is a “dictionary” that linearly spans the data space, and

·



indicates certain strategy for characterizing the error term E.

By choosing the dictionary as A = I and the regularization strategy

as E

, LRR identiﬁes RPCA. So, LRR is a generalization of

RPCA. In [6], it is shown that the problem of subspace segmentation

[24] can be well addressed by solving the following speciﬁc LRR

problems:

min

Z,E

Z

∗

+ λE

2,1

, s.t. X = XZ + E (6)

which is actually to set A = X and use the 

2,1

-norm to

characterize E in (5). Indeed, the above LRR method can also

address the problem of error correction, as illustrated in [6].

However, like RPCA, this method is also a transductive method and

cannot process new data efﬁciently. Namely, for a new datum x given,

this method essentially needs to recalculate over all the data (note that

each column of X is a data point), resulting in high computational

cost. Moreover, the 

2,1

-norm is chosen to model outliers and sample-

speciﬁc corruptions [23], and thus does not ﬁt well the random

corruptions addressed in this paper.

III. ROBUST ERROR CORRECTION BY IRPCA

The core of our IRPCA method is the learning of a low-rank

projection, which takes the role of projecting corrupted data vectors

onto the underlying subspace. The learning is done by solving a

convex optimization problem, as detailed in the following.

A. Pursue Low-Rank Projection by Convex Optimization

As mentioned above, the goal of IRPCA method is to own the

advantages of both PCA [8] and RPCA [9], [14], namely, not only can

well handle the data contaminated by gross corruptions but also own

good generalization ability for processing new data. Without impos-

ing any restriction on the corruptions, generally, it is impracticable to

achieve the goal of IRPCA. For example, if the corruptions are very

disordered as shown in Fig. 2(a), then there generally exists no simple

model for ﬁtting the corruptions. Fortunately, IRPCA is feasible due

to the following two facts. First, even if the corruptions are disordered

as in Fig. 2(a), there exists a linear projection P

that can project

any data point x onto the underlying subspace, and thus produce

accurate recovery results (although P

x may not exactly recover y in

this case). Second, note that two high-dimensional vectors, which

are generated independently, are almost orthogonal to each other

[25], i.e., the corruptions usually lie inside the null space of the

true subspace, as shown in Fig. 2(b). In this case, there exists a

linear projection P

for strictly removing the gross corruptions of

the data. Hence, given a data vector x generated in (1), we could

obtain its principal components y (or an approximation of y)by

using P

x,whereP

is the matrix that identiﬁes the underlying low-

rank projection. Provided that the data are of dimension d,thesize

of P

is d × d.

Up to present, the only left issue is to establish an algorithm for

learning the low-rank projection P

from a given set of training data.

According to the low rankness of the projection and the sparsity of

the noise, we may learn the low-rank projection P ∈

d×d

and the

principal components Y by solving the following problems:

min

P,Y

rank (P) + λX − PX

, s.t. Y = PX

where X =[x

,...,x

] is a data matrix consisting of a set of training

vectors, Y =[y

,...,y

] represents the principal components of X,

3796 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 21, NO. 8, AUGUST 2012

true subspace

corrupted points

corruption

(a)

true subspace

corrupted points

corruption

(b)

Fig. 2. (a) Corruptions are disordered. (b) Corruptions are orthogonal to the

true low-rank subspace.

·

denotes the 

-norm, i.e., the number of nonzero entries of a

matrix, and λ>0 is a parameter. Since X − PX identiﬁes the noise

E, we rewrite the above formulation into the following:

min

P,E

rank (P) + λE

, s.t. X = PX + E. (7)

The above optimization problem is difﬁcult to solve due to the

discrete nature of the rank function and the 

-norm. As a common

practice in rank minimization problems, we replace the rank function

with the nuclear-norm. Moreover, as suggested by [26], it is adequate

to replace the 

-norm with the 

-norm. Hence, we could learn

the low-rank projection by solving the following convex optimization

problems:

min

P,E

P

∗

+ λE

, s.t. X = PX + E. (8)

Suppose P

∗

is an optimal solution (with respect to the variable P)

to the above problem, then for any data vector x given, we could

estimate the principal components y and error part e by using P

∗

and x − P

∗

x, respectively.

B. Solving the Optimization Problem

Problem (8) can be solved in a similar way as the LRR problem

(6). One just needs to transform it into the following equivalent

problems:

min

P,E

P



∗

+ λE



, s.t. X

= X

+ E

According to the report in [6], the computational complexity of

solving (8) is O(d

), which is expensive for high-dimensional data.

For efﬁciency, we do not solve (8) directly, but instead to convert

(8) into a simpler problem by utilizing the theories established by

Liu et al. [23]. By Theorem 1 of [23], the transpose of the optimal

solution P

∗

always lies within the subspace spanned by the columns

of X. Namely, P

∗

can be factorized into the product of two matrices:

∗

= L

∗

)

,whereQ

∗

is computed by orthogonalizing the

columns of X. So, (8) can be equivalently converted into a simpler

problem by replacing P with L(Q

∗

)

min

L,E

L

∗

+ λE

, s.t. X = LA+ E (9)

Algorithm 1 Solving Problem (9) by Inexact ALM

Input: matrices X and A; parameter λ.

Initialize: L = J = 0, E = 0, Y

= 0, Y

= 0,μ =

−6

,μ

max

= 10

,ρ = 1.1, and ε = 10

−8

while not converged do

1. ﬁx the others and update J by

J = arg min

||J||

∗

||J − (Z +

)||

2. ﬁx the others and update L by

L = ((X − E) A

+ J +

− Y

)(I + AA

)

−1

3. ﬁx the others and update E by

E = arg min

||E||

||E − (X − LA+

)||

4. update the multipliers

= Y

+ μ(X − LA− E),

= Y

+ μ(Z − J)

5. update the parameter μ by μ = min(ρμ, μ

max

)

6. check the convergence conditions:

||X − LA− E||

∞

<εand ||Z − J||

∞

<ε

end while

Output: (L, E).

where A = (Q

∗

)

X. The above problem can be solved in the

same way as that for the LRR problem (5). For the competence

of presentation, the detailed optimization procedure is outlined in

Algorithm 1, which is based on the inexact argument Lagrange

multiplier (ALM) [27] method. Note that although Steps 1 and 3

of the algorithm are convex problems, they both have closed-form

solutions. Step 1 is solved via the singular value thresholding (SVT)

operator [28], while Step 3 is solved via the shrinkage operator [27].

Suppose (L

∗

, E

∗

) is an optimal solution to (9), then the optimal

solution to (8) can be recovered by (L

∗

)

, E

∗

). As the number

of the rows of A is at most k (k = rank (X) ≤ min(d, n)), the

computational complexity of Algorithm 1 is O(k

+ k

d + knd),

which is up bounded by O(n

+ n

d) (assume n ≤ d). So the

computation is quite efﬁcient if n (and/or d) is small. Also, the

computation cost of IRPCA is mainly spent in the training process.

After learning the projection P

∗

from the training data, it is very

efﬁcient for IRPCA to handle the new data. Namely, for any data

vector x given, we only need to calculate P

∗

C. Discussion

1) Connections With LRR:

The general LRR formula-

tion (5) can involve our IRPCA formulation (8). By setting A = X,

choosing E

and considering each row of X as a data point, then

(5) is identiﬁed to (8). So, IRPCA could be regarded as a special

example of LRR. Nevertheless, the IRPCA problem explored in this

paper has not been explored before. What has been explored in [6]

and [23] is the formulation (6), which is designed for subspace seg-

mentation in the presence of outliers and sample-speciﬁc corruptions.

Although the method based on (6) can be used for error correction

[6], like RPCA, this method is also a transductive method and cannot

process new data efﬁciently. Namely, for a new datum x given, this

评论收藏

内容反馈

yzy19900402

2016-04-14

论文资料整理的很全，东西不错，可以试一下的
wgy19882000

2018-06-24

可以参考~~~~~~
SaxtonLi

2016-04-03

非常给力的资源，很实用
唯爱酥酥

2018-11-22

最主要是代码能运行，good
shineyan1991

2018-04-15

论文中可以参考,感谢

前往

页

qq_16956901

粉丝: 9
资源: 8

RPCA最全文献和代码

rpca-master_rpca_python_alm_

代码 基于RPCA异常值检测代码

rpcamatlab代码-gemelli:Gemelli是一个工具箱，用于在稀疏成分组学数据集上运行稳健的AitchisonPCA（RPCA）

rpcamatlab代码-rpca_svs:使用RPCA进行语音分离的Python实现

RPCA经典论文

RPCA:RPCA的Python实现

rpcaADMM-master_python_rpca_admm_源码

pcp的rpca的matlab的代码-onlineRPCA:在线鲁棒主成分分析

rpcamatlab代码-frPCA_sparse:快速随机PCA用于稀疏数据

pcp的rpca的matlab的代码-ConcordiaUltrasound:协和超声

exact_alm_rpca_rpca_RPCA代码_alm背景分离_低秩稀疏_低秩.zip

基于RPCA异常值检测matlab代码.zip

3.MATLAB数据处理模型代码 基于RPCA异常值检测代码.rar

RPCA 源码 matlab yi Ma

RPCA图像去噪算法

RPCA的matlab实现

rpcamatlab代码-DEICODE:稀疏计数数据的强大AitchisonPCA

ialm_rpca背景建模

数据降维（RPCA,LRR.LE等）

MATLAB源码集锦-RPCA异常值检测代码

exact_alm_rpca_鲁棒pca去噪_RPCA代码_RPCA去噪_IALM_ＰＣＡ去噪_

exact_alm_rpca_rpca_RPCA代码_alm背景分离_低秩稀疏_低秩_源码.rar.rar

基于RPCA异常值检测代码.rar

RPCA.rar_RPCA去噪代码_RPCA图像去噪_considerys2_图像去噪_图像去噪增强

inexact_alm_rpca

RPCA 低秩稀疏分解

图像矩阵matlab代码-cuda-rpca-admm:使用ADMM进行优化以实现前景背景分离的鲁棒PCA的CUDA实现

matlab的egde源代码-fastRPCA:用于健壮PCA和SPCP的所有变体的Matlab代码

最新资源

代码基于RPCA异常值检测代码

3.MATLAB数据处理模型代码基于RPCA异常值检测代码.rar