![](https://csdnimg.cn/release/download_crawler_static/10890806/bg4.jpg)
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.