4
F. Matrix Completion
(Low Rank) Matrix Completion (MC) refers to the problem
of completing a rank
r
matrix
L
from a subset of its entries.
We use
Ω
to refer to the set of indices of the observed entries
of
L
and we use the notation
P
Ω
(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
L
from
M
. The set
Ω
is known.
To interpret this as a special case of RPCA, notice that one
can rewrite
M
as
M = L − P
Ω
c
(L)
where
Ω
c
refers to
the complement of the set
Ω
. By letting
S = −P
Ω
c
(L)
, this
becomes a special case of RPCA.
Identifiability. Like RPCA, this problem is also not iden-
tifiable in general. For example, if
L
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
L
are
µ
-incoherent as
defined above. In fact incoherence was first introduced for the
MC problem in [
26
], 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
L
; then, even with
the incoherence assumption, it is not possible to correctly
“interpolate” all the columns (rows) of
L
. 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 [
26
],
[29].
“Robust MC” (RMC) or “Robust PCA with Missing Data”
[
30
], [
31
] is an extension of both RPCA and MC. It involves
recovering
L
from
M
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
S
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 defined 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 find 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 fixed or slowly changing low-dimensional
subspace [
13
]. Another useful extension is undersampled or
compressive RPCA or robust Compressive Sensing (CS) [
32
],
[
33
], [
34
], [
35
], [
23
]. Instead of observing the matrix
M
, one
only has access to a set of
m < n
random linear projections
of each column of
M
, i.e., to
Z = AM
where
A
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 [
23
]. An alternative formulation is Robust CS where
one observes
Z := AS + L
[
32
], [
12
], [
33
], [
35
] and the
goal is to recover
S
while being robust to
L
. This would be
dynamic MRI problem if the low rank corruption
L
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 [
36
]. 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 first provably correct solution to robust PCA via S+LR
was introduced in parallel works by Candès, Wright, Li, and
Ma [
10
] (where they called it a solution to robust PCA) and
by Chandrasekharan et al. [
37
]. Both proposed to solve the
following convex program which was referred to as Principal
Component Pursuit (PCP) in [10]:
min
˜
L,
˜
S
k
˜
Lk
∗
+ λk
˜
Sk
vec(1)
subject to M =
˜
L +
˜
S
Here
kAk
vec(1)
denotes the vector
l
1
norm of the matrix
A
(sum of absolute values of all its entries) and
kAk
∗
denotes the
nuclear norm (sum of its singular values). PCP is the first known
polynomial time solution to RPCA that is also provably correct.
The two parallel papers [
10
], [
37
] used different approaches to
arrive at a correctness result for it. The result of [
38
] improved
that of [37].
Suppose that PCP can be solved exactly. Denote its solutions
by
ˆ
L,
ˆ
S. The result of [10] says the following.
Theorem 2.2.
Let
L
SVD
= U ΣV
0
be its reduced SVD. If
W =
0,
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
0
)
i,j
| ≤
r
µ
r
L
nd
3) support of S is generated uniformly at random,
4)
the support size of
S
, denoted
m
, and the rank of
L
,
r
L
,
satisfy:
m
nd
≤ c and r
L
≤
c min(n,d)
µ(log n)
2
,
the parameter
λ = 1/
p
max(n, d)
2
, then, with probability
at least
1 − cn
−10
, the PCP convex program with
λ =
1/
p
min(n, d) returns
ˆ
L = L and
ˆ
S = S.
The second condition (strong incoherence) requires that the
inner product between a row of
U
and a row of
V
be upper
bounded. Observe that the required bound is
1/
√
r
L
times
what left and right incoherence would imply (by using Cauchy-
Schwartz inequality). This is why it is a stronger requirement.
2
Notice that this requires no knowledge of model parameters.
剩余18页未读，继续阅读
音味
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测：静态代码分析与数据流方法
- 青苔数据CEO程永：技术生态与阿里云开放创新
- 制造业转型： HyperX引领企业上云策略
- 赵维五分享：航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器：设计与实现
- 猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
