RPCA_rpca_鲁棒_RPCAmatlab_鲁棒性_matlabcode_轴承频域特征参数有哪些资源-CSDN文库

共12个文件

zip：8个

pdf：4个

版权申诉

rpca

matlabcode

5星 · 超过95%的资源 129 浏览量 2021-09-11 16:13:53 上传评论 3 收藏 2.72MB RAR 举报

RPCA，全称为Robust Principal Component Analysis（鲁棒主成分分析），是一种在处理含有噪声、异常值或缺失数据的高维矩阵时，用于提取主要成分的统计方法。它结合了主成分分析（PCA）和稀疏分解的概念，旨在增强对异常值的鲁棒性。在PCA中，数据被投影到低秩空间以保留大部分方差，但在有异常值的情况下，PCA可能受到严重影响。RPCA通过将数据矩阵分解为低秩和稀疏两个部分来解决这个问题。在MATLAB中实现RPCA，通常会使用一种名为“RPCA算法”的优化方法，如“LMaFit”或“ProPCA”。这些算法的核心是交替最小化问题，即在保持一个矩阵低秩的同时，另一个矩阵尽可能地稀疏。具体来说，数据矩阵X被分解为L+S，其中L是低秩矩阵，S是稀疏矩阵。这个过程可以表示为一个优化问题： \[ \min_{L,S} rank(L) + \lambda \|S\|_1 \quad s.t. \quad L + S = X \] 这里的λ是一个正则化参数，控制稀疏度和低秩之间的平衡。在MATLAB代码中，这通常通过使用稀疏编码和低秩分解的迭代算法来实现。 MATLAB代码示例可能会包括以下几个关键步骤： 1. 初始化：设置L和S的初始值，通常L初始化为X的奇异值分解（SVD）的前几个奇异值构成的矩阵，S初始化为零矩阵。 2. 迭代更新：在每一步迭代中，交替更新L和S，直到达到预设的收敛条件。对于L，可以通过最小化核范数（等价于矩阵的rank）来更新；对于S，可以利用软阈值函数来促进稀疏性。 3. 收敛检查：比较连续两次迭代的L和S的变化量，如果变化小于某个阈值，则认为已经收敛。在实际应用中，RPCA广泛应用于图像去噪、视频背景建模、推荐系统、网络异常检测等领域。例如，在视频处理中，背景通常被认为是低秩的，而运动物体或光照变化可以视为稀疏的噪声。通过RPCA，可以有效地分离这两部分，从而实现背景扣除。需要注意的是，选择合适的λ至关重要，因为它直接影响到结果的低秩性和稀疏性的平衡。如果λ太小，S可能不够稀疏，无法有效去除异常值；如果λ太大，L可能过于简化，丢失了重要信息。因此，通常需要通过交叉验证或根据实际应用场景调整λ的值。 RPCA是数据分析和机器学习领域的一种强大工具，通过结合PCA的高效降维能力和稀疏表示的异常检测能力，可以在有噪声或异常值的数据中挖掘出有用的信息。在MATLAB中实现RPCA，需要理解其背后的数学原理，并熟悉相关的优化算法，才能编写出有效的代码。

资源详情

资源评论

资源推荐

收起资源包目录

RPCA_rpca_鲁棒_RPCAmatlab_鲁棒性_matlabcode_源码.rar （12个子文件）

RPCA

Singular Value Thresholding code

0810.3286.pdf 325KB

svt.zip 3KB

Alternating Direction Method

2447.pdf 264KB

LRSD-Code.zip 5KB

dual.zip 380KB

SVDcode

apg.zip 4KB

dual method.zip 380KB

rpca_algorithms.pdf 248KB

apg_partial.zip 373KB

Augmented Lagrange Multiplier (ALM) Method

The Augmented Lagrange Multiplier Method for.pdf 295KB

inexact_alm_rpca.zip 372KB

exact_alm_rpca.zip 372KB

arXiv:0810.3286v1 [math.OC] 18 Oct 2008

A Singular Value Thresholding Algorithm for Matrix Completion

Jian-Feng Cai

†

Emmanuel J. Cand`es

♯

Zuowei Shen

† Temasek Laboratories, National University o f Singapore, Singapore 117543

♯ Applied and Computational Mathematics, Caltech, Pasadena, CA 91125

§ Department of Mathematics, National University of Singapore, Singapore 11 7543

September 2008

Abstract

This paper intr oduces a novel algorithm to approximate the matrix with minimum nuclear

norm among all matrices obeying a set of convex constraints. This pr oblem may be understood as

the convex relaxation of a rank minimization problem, and arise s in many importa nt applications

as in the task of re covering a large matrix from a small subset of its entries (the famous Netﬂix

problem). Oﬀ-the-shelf algorithms such as interior point methods are not directly amenable to

large problems of this kind with over a million unknown entries.

This paper develops a simple ﬁrst-order and easy-to-implement algorithm that is extremely

eﬃcient at a ddressing problems in which the optimal solution has low rank. The algorithm is

iterative and produces a se quence of matrices {X

, Y

} and at each step, mainly perfor ms a

soft-thresholding opera tion on the singular values of the matrix Y

. There are two re markable

features making this attractive for low-rank matrix completion problems. The ﬁr st is that

the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of

the iterates {X

} is empirically nondecreasing. Both these facts allow the algorithm to make

use of very minimal storage spac e and keep the computational cost of each iteration low. On

the theoretical side, we provide a convergence analysis showing that the sequence of itera tes

converges. On the practical side, we provide numerical examples in which 1, 000×1, 000 matrices

are recovered in less than a minute on a modest desktop computer. We also demonstrate that

our approach is amenable to very larg e scale problems by recovering matr ic e s of rank about 10

with nearly a billion unknowns from just about 0.4% of their sampled entries. Our methods are

connected with the recent literatur e on linearized Bregman iterations for ℓ

minimization, and

we develop a framework in which one can understand these algorithms in terms of well-known

Lagrange multiplier algo rithms.

Keywords. Nuclear norm minimization, matrix completion , singular value thresholding, La-

grange dual function, Uzawa’s algorithm.

1 Introduction

1.1 Motivation

There is a rapidly growing interest in the recovery of an unknown low-rank or approximately low-

rank matrix from very limited information. This pr ob lem occurs in many areas of engineering and

applied science such as mach ine learning [1, 3, 4], control [42] and computer vision, see [48]. As

a motivating example, consider the problem of recovering a data matrix from a sampling of its

entries. This routinely comes up whenever one collects partially ﬁlled out surveys, and one would

like to infer the many missing entries. In the area of recommender systems, users subm it ratings

on a subset of entries in a database, and the vendor provides recommendations based on the user’s

preferences. Because users only rate a few items, one would like to infer their pr eference for unrated

items; this is the famous Netﬂix problem [2]. Recovering a rectangular matrix from a sampling of

its entries is known as the matrix completion problem. The issue is of course that this problem is

extraordinarily ill posed since with fewer samples than entries, we have in ﬁnitely many completions.

Therefore, it is apparently impossible to identify which of these candidate solutions is indeed the

“correct” one without some additional information.

In many instances, however, the matrix we wish to recover has low rank or approximately low

rank. For instance, the Netﬂix data matrix of all user-ratings may be app roximately low-rank

because it is commonly believed that on ly a few factors contribute to anyone’s taste or preference.

In computer vision, inferring scene geometry and camera motion from a sequence of images is a well-

studied problem know n as the structure-from-motion problem. This is an ill-conditioned problem

for objects may be d istant with respect to their size, or especially for “missing data” which occur

because of occlusion or tracking failures. However, when p roperly stacked and indexed, these images

form a matrix which has very low rank (e.g. rank 3 under orthography) [21, 48]. Other examples

of low-rank matrix ﬁtting aboun d; e.g. in control (system identiﬁcation), machine learning (multi-

class learning) and so on. Having said this, the premise that the unknown has (approximately) low

rank radically changes the problem, making the search for solutions feasible since the lowest-rank

solution now tends to be the right one.

In a recent p aper [13], Cand`es and Recht showed that matrix completion is not as ill-posed as

people thought. Indeed, they proved that most low-rank matrices can be recovered exactly from

most sets of sampled entries even though these sets have su rprisingly small cardinality, and more

importantly, they p roved that this can be done by solving a simple convex optimization problem.

To state their results, suppose to simplify that the unknown matrix M ∈ R

n×n

is square, and that

one has available m sampled entries {M

: (i, j) ∈ Ω} where Ω is a rand om subset of cardinality

m. Then [13] proves that most matrices M of rank r can be perfectly r ecovered by solving the

optimization problem

minimize kXk

∗

subject to X

= M

, (i, j) ∈ Ω,

(1.1)

provided that the number of samples obeys

m ≥ Cn

6/5

r log n (1.2)

for some positive numerical constant C.

In (1.1), the functional kXk

∗

is the nuclear norm of the

matrix M, which is the sum of its singular values. The optimization problem (1.1) is convex and

can be recast as a semideﬁnite program [29,30]. In some sense, this is the tightest convex relaxation

of the NP-hard rank minimization problem

minimize rank(X)

subject to X

= M

, (i, j) ∈ Ω,

(1.3)

Note that an n × n matrix of rank r depends upon r(2n − r) degrees of freedom.

since the nuclear ball {X : kXk

∗

≤ 1} is the convex hull of the set of rank-one m atrices with

spectral norm bounded by one. Another interpretation of Cand`es and Recht’s result is that under

suitable conditions, the rank minimization program (1.3) and the convex program (1.1) are formally

equivalent in th e sense that they have exactly the same unique solution.

1.2 Algorithm outline

Because minimizing the nuclear norm both provably recovers the lowest-rank m atrix subject to

constraints (see [45] for related results) and gives generally good empirical results in a variety of

situations, it is understandably of great interest to develop numerical methods for solving (1.1). In

[13], this optimization problem was solved using on e of the most advanced semideﬁnite programming

solvers, namely, SDPT3 [47]. This solver and others like SeDuMi are based on interior-point

methods, and are problematic when the size of the m atrix is large because they need to solve huge

systems of linear equations to compute the Newton d irection . In fact, SDPT3 can only handle

n ×n matrices with n ≤ 100. Presumably, one could resort to iterative solvers such as the method

of conjugate gradients to solve for the Newton step bu t th is is problematic as well since it is well

known that the condition number of the Newton system increases rapidly as one gets closer to the

solution. In addition, none of these general purpose solvers use the fact that the solution may have

low rank. We refer the reader to [40] for some recent p rogress on inter ior-point methods concerning

some special nuclear norm-minimization problems.

This paper develops the singu lar value thresholding algorithm for approximately solving the

nuclear norm min imization problem (1.1) and by extension, problems of the form

minimize kXk

∗

subject to A(X) = b,

(1.4)

where A is a linear operator acting on the space of n

×n

matrices and b ∈ R

. This algorithm is

a simple ﬁrst-order method, and is especially well suited for problems of very large sizes in which

the solution has low rank. We sketch this algorith m in the special matrix completion setting and

let P

Ω

be the orthogonal p roj ector onto the span of matrices vanishing outside of Ω so that the

(i, j)th component of P

Ω

(X) is equal to X

if (i, j) ∈ Ω and zero otherwise. Our problem may be

expressed as

minimize kXk

∗

subject to P

Ω

(X) = P

Ω

(M),

(1.5)

with optimization variable X ∈ R

×n

. Fix τ > 0 and a sequence {δ

}

k≥1

of scalar step sizes.

Then starting with Y

= 0 ∈ R

×n

, the algorithm in ductively deﬁnes

(

= shrink(Y

k−1

, τ),

= Y

k−1

+ δ

Ω

(M − X

)

(1.6)

until a stopp ing criterion is reached. In (1.6), shrink(Y , τ ) is a nonlinear function which applies a

soft-thresholding rule at level τ to the singular values of the input matrix, see Section 2 for details.

The key property here is that for large values of τ, the sequence {X

} converges to a solution which

very nearly minimizes (1.5). Hence, at each step, one only needs to compute at most one singular

value decomposition and perform a few elementary matrix additions. Two important remarks are

in order:

1. Sparsity. For each k ≥ 0, Y

vanishes outside of Ω and is, therefore, sparse, a fact which can

be us ed to evaluate the shrink function rapidly.

2. Low-rank property. The matrices X

turn out to have low rank, and hence the algorithm has

minimum storage r equirement since we only need to keep principal factors in memory.

Our num erical experiments demonstrate that the proposed algorithm can solve problems, in

Matlab, involving matrices of size 30, 000×30, 000 having close to a billion unkn owns in 17 minutes

on a standard desktop computer with a 1.86 GHz C P U (dual core with Matlab’s multithreading

option enabled) and 3 GB of memory. As a consequence, the singular value thresholding algorithm

may become a rather powerf ul computational tool for large scale matrix completion.

1.3 General formulation

The singular value thresholding algorithm can be adapted to deal with other types of convex

constraints. For instance, it m ay address problems of the form

minimize kXk

∗

subject to f

(X) ≤ 0, i = 1, . . . , m,

(1.7)

where each f

is a Lipschitz convex fun ction (note that one can handle linear equality constraints by

considering pairs of aﬃne functionals). In the simp ler case where the f

’s are aﬃne functionals, the

general algorithm goes through a sequence of iterations which greatly resemble (1.6). This is useful

because this enables the development of numerical algorithms which are eﬀective for recovering

matrices from a small subset of sampled entries possibly contaminated with noise.

1.4 Contents and notations

The rest of the paper is organized as follows. In S ection 2, we derive the singular value threshold-

ing (SVT) algorithm for the matrix completion problem, and recasts it in terms of a well-known

Lagrange multiplier algorithm. In Section 3, we extend th e SVT algorithm and formulate a gen-

eral iteration which is applicable to general convex constraints. In Section 4, we establish the

convergence results for the iteration s given in Sections 2 and 3. We demonstrate the performance

and eﬀectiveness of the algorith m thr ou gh numerical examples in Section 5, and review additional

implementation details. Finally, we conclude the paper with a short discussion in Section 6.

Before continuing, we provide here a brief summary of the notations used throughout the

paper. Matrices are bold capital, vectors are bold lowercase and scalars or entries are not bold.

For instance, X is a matrix and X

its (i, j)th entry. Likewise, x is a vector and x

its ith

component. The nuclear norm of a matrix is denoted by kXk

∗

, the Frobenius norm by kXk

and the spectral norm by kXk

; note that these are respectively the 1-norm, the 2-norm and the

sup-norm of the vector of singular values. The adjoint of a matrix X is X

∗

and similarly for

vectors. The notation diag(x), where x is a vector, s tands for the diagonal matrix with {x

} as

diagonal elements. We denote by hX, Y i = trace(X

∗

Y ) the standard inner product between two

matrices (kXk

= hX, Xi). The Cauchy-S chwarz inequality gives hX, Y i ≤ kXk

kY k

and it is

well known that we also have hX, Y i ≤ kXk

∗

kY k

(the spectral and nuclear norms are dual from

one another), see e.g. [13, 45].

2 The Singular Value Thresholding Algorithm

This section introduces th e s ingular value thresholding algorithm and discusses some of its ba-

sic properties. We begin with the deﬁnition of a key building blo ck, namely, the singular value

thresholding operator.

2.1 The singular value shrinkage operator

Consider the singular value decomposition (SVD) of a matrix X ∈ R

×n

of ran k r

X = U ΣV

∗

, Σ = diag ({σ

}

1≤i≤r

), (2.1)

where U and V are respectively n

× r and n

× r matrices with orthonormal columns, and the

singular values σ

are positive (unless speciﬁed otherwise, we will always assume that the SVD of

a matrix is given in the reduced f orm above). For each τ ≥ 0, we introduce the soft-thresholding

operator D

deﬁned as follows:

(X) := U D

(Σ)V

∗

, D

(Σ) = diag({σ

− τ )

}), (2.2)

where t

is the positive part of t, namely, t

= max(0, t). In words, this operator simply applies a

soft-thresholding rule to the singular values of X, eﬀectively shrin king these towards zero. This is

the reason why we will also refer to this transformation as the singular value shrinkage operator.

Even though the SVD may n ot be unique, it is easy to see that the singular value shr inkage operator

is well deﬁned and we do not elaborate further on this issue. In some sen se, this shrin kage operator

is a straightforward extension of the soft-thresholding rule for scalars and vectors. In particular,

note that if many of the singular values of X are below the thresh old τ, the rank of D

(X) may

be considerably lower than that of X, just like the soft-thresholding rule applied to vectors leads

to sparser outputs whenever some entries of the input are below threshold.

The singular value thr esholding operator is the proximity operator associated with the nuclear

norm. Details about the proximity operator can be found in e.g. [35].

Theorem 2.1 For each τ ≥ 0 and Y ∈ R

×n

, the singular value shrinkage operator (2.2) obeys

(Y ) = arg min



kX − Y k

+ τ kXk

∗



. (2.3)

Proof. Since the function h

(X) := τkXk

∗

kX −Y k

is strictly convex, it is easy to see that

there exists a un ique minimizer, and we thus need to prove that it is equal to D

(Y ). To do this,

recall the deﬁnition of a subgradient of a convex function f : R

×n

→ R. We say that Z is a

subgradient of f at X

, d en oted Z ∈ ∂f(X

), if

f(X) ≥ f (X

) + hZ, X − X

i (2.4)

for all X. Now

X minimizes h

if and only if 0 is a subgradient of the functional h

at the point

X, i.e.

0 ∈

X − Y + τ∂k

∗

, (2.5)

where ∂k

∗

is the set of subgradients of the nuclear norm. Let X ∈ R

×n

be an arbitrary

matrix and U ΣV

∗

be its SVD. It is know n [13, 37, 49] that

∂kXk

∗



∗

+ W : W ∈ R

×n

, U

∗

W = 0, W V = 0, kW k

≤ 1



. (2.6)

RongLinQin

2022-03-30

用户下载后在一定时间内未进行评价，系统默认好评。

评论收藏

内容反馈

版权申诉

心梓

粉丝: 846
资源: 8043

RPCA_rpca_鲁棒_RPCAmatlab_鲁棒性_matlabcode

评论9

最新资源

RPCA_rpca_鲁棒_RPCAmatlab_鲁棒性_matlabcode

评论9

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

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

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

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

pcp的rpca的matlab的代码-Trent:特伦特

matlab RPCA程序代码.rar

RPCA的matlab实现

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

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

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

RPCA_rpca_鲁棒_RPCAmatlab_鲁棒性_matlabcode_源码.rar.rar

RPCA_rpca_鲁棒_RPCAmatlab_鲁棒性_matlabcode_源码.zip

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

dual_rpca.rar_RPCA matlab_dual_rpca_matlab RPCA_rpca_图像RPCA MAT

WSNM_RPCA_p_oncee78_healthgqn_weightedschatten_schatten-p_rpca_源

exact_alm_rpca.zip_Exact ALM_alm_exact_alm_exact_alm_rpca_鲁棒

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

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

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

RPCA 源码 matlab yi Ma

rpcamatlab代码-Enhanced-3DTV:增强型3DTV正则化代码及其在高光谱图像降噪和压缩感知中的应用

RPCA最全文献和代码

RPCA分解MATLAB

RPCA 低秩稀疏分解

图像盲分离matlab代码-rPCA-MWF:rPCA-MWF

RPCA图像去噪算法

GoDec稀疏加低秩表示

rpca-master_rpca_python_alm_

RPCA异常值检测代码_RPCA检测_rpca_最优权_j进阶算法_secreta67_

最新资源

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