低秩矩阵修补与动态RPCA：理论与应用综述

需积分: 10 147 浏览量更新于2024-07-17 收藏 1.18MB PDF 举报

"这篇文章是关于2018年CANDES会议上关于静态与动态鲁棒主成分分析（RPCA）和矩阵填充的综述。作者Namrata Vaswani和Praneeth Narayanamurthy回顾了过去十年在RPCA领域的研究成果，特别是如何处理数据中的异常值，以及如何在数据子空间随时间变化时进行有效的跟踪。RPCA在机器学习、数据分析、协同过滤、降维处理、多任务学习和模式识别等多个领域有着广泛应用。" 在机器学习和数据分析中，低秩矩阵修复技术已经成为了关键问题。它主要处理的是那些可以通过少数样本或观察来近似表示的高维数据，例如在协同过滤中，通过用户的少量行为推断他们可能的喜好；在降维处理中，通过找到数据的主要成分来降低复杂度，便于分析；在多任务学习中，利用各任务间的共享信息来提升整体性能；而在模式识别中，低秩假设有助于发现隐藏的结构和模式。主成分分析（PCA）是最常用的降维方法之一，它能找出数据的主要方向并投影数据到这些方向上。然而，当数据受到异常值（outliers）的影响时，传统的PCA可能会失效。鲁棒主成分分析（RPCA）应运而生，它的目标是在异常值存在的情况下依然能提取数据的主要成分。Candès、Wright、Li和Madeﬁ的工作提出了将数据矩阵分解为低秩矩阵（代表正常数据）和稀疏矩阵（代表异常值）的框架。低秩部分提供了PCA的解决方案，因为它捕获了数据的主要结构，而稀疏部分则捕获了异常的、不常见的或者噪声的部分。随着数据动态性的增加，动态RPCA（或称为鲁棒子空间跟踪）成为了一个新的研究焦点。这一方法旨在跟踪数据在缓慢变化的子空间中的运动，同时对稀疏异常值保持鲁棒性。这对于监控和预测系统特别有用，比如视频监控中背景与运动物体的分离，或者网络流量分析中正常流量与异常流量的区分。过去十年的研究中，学者们提出了一系列理论证明正确、快速且内存效率高的RPCA求解和动态跟踪算法。这些工作不仅提升了RPCA在实际应用中的性能，也为未来的研究提供了坚实的基础。综述文章详细阐述了这些进展，包括理论分析、算法设计和实证结果，对于理解和应用RPCA及其动态版本具有极大的参考价值。

F. Matrix Completion

(Low Rank) Matrix Completion (MC) refers to the problem

of completing a rank

matrix

from a subset of its entries.

We use

Ω

to refer to the set of indices of the observed entries

and we use the notation

Ω

(M )

to refer to the matrix

formed by setting the unobserved entries to zero. Thus, given

M := P

Ω

(L)

the goal of MC is to recover

from

. The set

Ω

is known.

To interpret this as a special case of RPCA, notice that one

can rewrite

M = L − P

Ω

(L)

where

Ω

refers to

the complement of the set

Ω

. By letting

S = −P

Ω

(L)

, this

becomes a special case of RPCA.

Identiﬁability. Like RPCA, this problem is also not iden-

tiﬁable in general. For example, if

is low-rank and sparse

and if one of its nonzero entries is missing there is no way to

“interpolate” the missing entry from the observed entries without

extra assumptions. This issue can be resolved by assuming that

the left and right singular vectors of

are

-incoherent as

deﬁned above. In fact incoherence was ﬁrst introduced for the

MC problem in [

], and later used for RPCA. Similarly, it is

also problematic if the set

Ω

contains all entries corresponding

to just one or two columns (or rows) of

; then, even with

the incoherence assumption, it is not possible to correctly

“interpolate” all the columns (rows) of

. This problem can be

resolved by assuming that

Ω

is generated uniformly at random

(or according to the iid Bernoulli model) with a lower bound

on its size. For a detailed discussion of this issue, see [

[29].

“Robust MC” (RMC) or “Robust PCA with Missing Data”

[

], [

] is an extension of both RPCA and MC. It involves

recovering

from

when

M = P

Ω

(L + S)

. Thus the

entries are corrupted and not all of them are even observed.

In this case there is no way to recover

of course. Also, the

only problematic outliers are the ones that correspond to the

observed entries since M = P

Ω

(L) + P

Ω

(S).

Dynamic MC is the same as the problem of subspace tracking

with missing data (ST-missing). This can be deﬁned in a fashion

analogous to the RST problem described above. Similarly for

dynamic RMC.

G. Other Extensions

In many of the applications of RPCA, the practical goal

is often to ﬁnd the outlier or the outlier locations (outlier

support). For example, this is often the case in the video

analytics application. This is also the case in the anomaly

detection application. In these situations, robust PCA should

really be called “robust sparse recovery”, or “sparse recovery

in large but structured noise”, with “structure” meaning that

the noise lie in a ﬁxed or slowly changing low-dimensional

subspace [

]. Another useful extension is undersampled or

compressive RPCA or robust Compressive Sensing (CS) [

[

], [

]. Instead of observing the matrix

, one

only has access to a set of

m < n

random linear projections

of each column of

, i.e., to

Z = AM

where

is a fat

matrix. An important application of this setting is in dynamic

MRI imaging when the image sequence is modeled as sparse +

low-rank [

]. An alternative formulation is Robust CS where

one observes

Z := AS + L

[

], [

] and the

goal is to recover

while being robust to

. This would be

dynamic MRI problem if the low rank corruption

is due to

measurement noise.

II. RPCA SOLUTIONS

Before we begin, we should mention that the code for all

the methods described in this section is downloadable from

the github library of Andrew Sobral [

]. The link is https:

//github.com/andrewssobral/lrslibrary.

Also, in the guarantees given in this article, for simplicity,

the condition number is assumed to be constant, i.e.,

O(1)

with n.

A. Principal Component Pursuit (PCP): a convex programming

solution

The ﬁrst provably correct solution to robust PCA via S+LR

was introduced in parallel works by Candès, Wright, Li, and

Ma [

] (where they called it a solution to robust PCA) and

by Chandrasekharan et al. [

]. Both proposed to solve the

following convex program which was referred to as Principal

Component Pursuit (PCP) in [10]:

min

∗

+ λk

vec(1)

subject to M =

L +

Here

kAk

vec(1)

denotes the vector

norm of the matrix

(sum of absolute values of all its entries) and

kAk

∗

denotes the

nuclear norm (sum of its singular values). PCP is the ﬁrst known

polynomial time solution to RPCA that is also provably correct.

The two parallel papers [

], [

] used different approaches to

arrive at a correctness result for it. The result of [

] improved

that of [37].

Suppose that PCP can be solved exactly. Denote its solutions

S. The result of [10] says the following.

Theorem 2.2.

Let

SVD

= U ΣV

be its reduced SVD. If

W =

1) U is µ-incoherent, V is µ-incoherent,

2) U and V are µ-strong-incoherent, i.e. satisfy

max

i=1,2,...,n,j=1,2,...,d

|(U V

)

i,j

| ≤

3) support of S is generated uniformly at random,

the support size of

, denoted

, and the rank of

satisfy:

≤ c and r

≤

c min(n,d)

µ(log n)

the parameter

λ = 1/

max(n, d)

, then, with probability

at least

1 − cn

−10

, the PCP convex program with

λ =

min(n, d) returns

L = L and

S = S.

The second condition (strong incoherence) requires that the

inner product between a row of

and a row of

be upper

bounded. Observe that the required bound is

√

times

what left and right incoherence would imply (by using Cauchy-

Schwartz inequality). This is why it is a stronger requirement.

Notice that this requires no knowledge of model parameters.

剩余18页未读，继续阅读

音味

粉丝: 0
资源: 1

低秩矩阵修补与动态RPCA：理论与应用综述

RPCA经典论文

jsp参考文献jsp参考文献jsp参考文献jsp参考文献

java的参考文献

Candes.rar_robust uncertainty

2008年IEEE information theory best paper award ( Terry Tao Candes &Donoho)

deep-learning-uncertainty:文献调查，论文审阅，实验设置以及用于深度学习模型中的预测不确定性估计的基线方法的实现的集合

基于Gabor-Curvelet联合变换的雷达Chirp信号检测与估计 (2011年)

脊波理论与应用：Ridgelets 分析经典文献

深度学习中的预测不确定性：文献综述与基线实现

矩阵填充算法的最新进展与应用分析

最新资源