IEEE Signal Processing - July 2018 - 37
need to redefine max-outlier-frac-row as
Technically, dynamic RPCA is the
One way to ensure that
the maximum nonzero fraction per row in
offline version of the aforementioned probL is not sparse is by
any a-consecutive-column submatrix of
lem. Define matr ices L, S, W, M with
requiring that its left and
L = [, 1, , 2, f, d] and M, S, W similarly
S. We refer to it as max-outlier-frac-rowa.
right singular vectors are
defined. The goal is to recover the matrix L
Here a is the mini-batch size used by the
dense or "incoherent" with RST algorithm.
and its column space with e error.
t t l) P t o
respect to a sparse vector.
Lastly, as we will see, if one also assumes
We u s e SE (Pt , P) : = (I - PP
a lower bound on outlier magnitudes (uses
measure the subspace error (distance)
the model that outliers are large magnitude
between the subspaces spanned by the colcorruptions), it can help significantly relax the required upper
umns of P and Pt . This measures the sine of the maximum
bound on max-outlier-frac-rowa, while also allowing for a fast,
principal angle between the two subspaces. It is symmetric
when the two subspaces have equal dimension. Here and elseonline, and memory-efficient algorithm.
where $ denotes the induced l 2 norm and ' denotes matrix
transpose.
Static robust principal component analysis: A summary
The first provably correct and polynomial complexity solution
to RPCA was introduced in [4]. It involves solving a convex
Identifiability and other assumptions
program that they called PC pursuit (PCP). The same program
The previously given problem definitions do not ensure identiwas introduced and studied in parallel [5] and later work [6]
fiability since either L or S can be both low rank and sparse.
as an S+LR solution. While polynomial complexity is better
For the unfamiliar reader, we explain this point in detail in
than exponential, it is still too slow for today's big data sets.
the section "Understanding Identifiability Issues." One way to
Moreover, the number of iterations needed for a convex proensure that L is not sparse is by requiring that its left and right
gram solver to get to within an e ball of the true solution of the
singular vectors are dense or "incoherent" with respect to a
sparse vector [4].
convex program is O (1/e), and thus the typical complexity for
a PCP solver is O (nd 2 /e) [8]. To address this issue, a provably
correct alternating minimization (alt-min) solution called AltDefinition 2.1 (μ-incoherence/denseness)
Proj was introduced in [8]. This has much lower time complexn
#
r
We say that an
basis matrix (a matrix with mutually
ity and still works under the same assumptions as PCP. The
orthonormal columns) P is μ-incoherent if
following holds [8].
2
max P (i) # n rL ,
i = 1, 2, f, n
n
where P (i) denotes the ith row of P and n $ 1 is the (in)coherence parameter. It quantifies the nondenseness of P.
One way to ensure that S is not low rank is by imposing upper bounds on max-outlier-frac-row and max-outlierfrac-col.
Consider the RST problem. If the r-dimensional subspaces
change at each time, there are too many unknown parameters
making the subspace tracking problem unidentifiable. One
way to ensure identifiability is to assume that they are piecewise constant [7], [27], i.e., that
P(t) = Pj for all t ! [t j, t j + 1), j = 1, 2, f , J,
with t 0 = 1 and t J + 1 = d, and to lower bound t j + 1 - t j by
a number more than r. With this model, rL = rJ in general
(except if subspace directions are repeated more than once).
Left and right incoherence of L and outlier fraction bounds
on S are again needed. The union of the column spans of all
the Pj s is equal to the span of the left singular vectors of L.
Thus, left incoherence is equivalent to assuming that the Pj s
are μ-incoherent. One can replace right incoherence by an independent identically distributed assumption on the a t s, along
with boundedness of each element of a t. As explained in [27],
the two assumptions are similar. The latter is more suited for
RST since it involves online estimation. Since RST algorithms
are online and often operate on mini-batches of data, we also
Theorem 2.2 (Alternating projection guarantee for robust
principal component analysis)
SVD
Let L = URV l. If 1) U, V are μ-incoherent, 2) max (max2
outlier-frac-row, max-outlier-frac-col) # ncrL , 3) W F # Ce 2,
and 4) algorithm parameters are appropriately set, then AltProj
returns Lt , St with Lt - L F # e, and St - S max # e/ md in
time O (ndr 2L log (1/e)) .
An even faster solution that relied on projected gradient descent (GD), called RPCA-GD, was proposed in [10]. If
condition numbers are treated as constants, its complexity is
only O (ndrL log (1/e)) . This is comparable to that of vanilla
r-SVD for simple PCA; however, this approach needs outlier
fraction bounds to be rL times tighter. Another algorithm
that relies on the recursive projected compressive sensing
(CS) (ReProCS) approach and has the same time complexity as RPCA-GD is called nearly optimal RST via ReProCS
(ReProCS-NORST) [27], [28]. This is also online (after initialization); has much lower, and nearly optimal, memory complexity of O (nrL log n log (1/e)); and has outlier tolerance that
is better than even AltProj. But it needs two extra assumptions:
lower bound on most outlier magnitudes, and fixed or slow
subspace change. For a similar setting, a recent RMC solution, called nearly optimal RMC (NO-RMC), is also applicable
[17]. It is the fastest RPCA solution with a time complexity of
just O (nr 2L log 2 n log 2 (1/e)), but it needs d . n. As we explain
later, this is a strong assumption for video data. It achieves this
speed-up by deliberately undersampling M and solving RMC.
IEEE Signal Processing Magazine
|
July 2018
|
37
Table of Contents for the Digital Edition of IEEE Signal Processing - July 2018
Contents
IEEE Signal Processing - July 2018 - Cover1
IEEE Signal Processing - July 2018 - Cover2
IEEE Signal Processing - July 2018 - Contents
IEEE Signal Processing - July 2018 - 2
IEEE Signal Processing - July 2018 - 3
IEEE Signal Processing - July 2018 - 4
IEEE Signal Processing - July 2018 - 5
IEEE Signal Processing - July 2018 - 6
IEEE Signal Processing - July 2018 - 7
IEEE Signal Processing - July 2018 - 8
IEEE Signal Processing - July 2018 - 9
IEEE Signal Processing - July 2018 - 10
IEEE Signal Processing - July 2018 - 11
IEEE Signal Processing - July 2018 - 12
IEEE Signal Processing - July 2018 - 13
IEEE Signal Processing - July 2018 - 14
IEEE Signal Processing - July 2018 - 15
IEEE Signal Processing - July 2018 - 16
IEEE Signal Processing - July 2018 - 17
IEEE Signal Processing - July 2018 - 18
IEEE Signal Processing - July 2018 - 19
IEEE Signal Processing - July 2018 - 20
IEEE Signal Processing - July 2018 - 21
IEEE Signal Processing - July 2018 - 22
IEEE Signal Processing - July 2018 - 23
IEEE Signal Processing - July 2018 - 24
IEEE Signal Processing - July 2018 - 25
IEEE Signal Processing - July 2018 - 26
IEEE Signal Processing - July 2018 - 27
IEEE Signal Processing - July 2018 - 28
IEEE Signal Processing - July 2018 - 29
IEEE Signal Processing - July 2018 - 30
IEEE Signal Processing - July 2018 - 31
IEEE Signal Processing - July 2018 - 32
IEEE Signal Processing - July 2018 - 33
IEEE Signal Processing - July 2018 - 34
IEEE Signal Processing - July 2018 - 35
IEEE Signal Processing - July 2018 - 36
IEEE Signal Processing - July 2018 - 37
IEEE Signal Processing - July 2018 - 38
IEEE Signal Processing - July 2018 - 39
IEEE Signal Processing - July 2018 - 40
IEEE Signal Processing - July 2018 - 41
IEEE Signal Processing - July 2018 - 42
IEEE Signal Processing - July 2018 - 43
IEEE Signal Processing - July 2018 - 44
IEEE Signal Processing - July 2018 - 45
IEEE Signal Processing - July 2018 - 46
IEEE Signal Processing - July 2018 - 47
IEEE Signal Processing - July 2018 - 48
IEEE Signal Processing - July 2018 - 49
IEEE Signal Processing - July 2018 - 50
IEEE Signal Processing - July 2018 - 51
IEEE Signal Processing - July 2018 - 52
IEEE Signal Processing - July 2018 - 53
IEEE Signal Processing - July 2018 - 54
IEEE Signal Processing - July 2018 - 55
IEEE Signal Processing - July 2018 - 56
IEEE Signal Processing - July 2018 - 57
IEEE Signal Processing - July 2018 - 58
IEEE Signal Processing - July 2018 - 59
IEEE Signal Processing - July 2018 - 60
IEEE Signal Processing - July 2018 - 61
IEEE Signal Processing - July 2018 - 62
IEEE Signal Processing - July 2018 - 63
IEEE Signal Processing - July 2018 - 64
IEEE Signal Processing - July 2018 - 65
IEEE Signal Processing - July 2018 - 66
IEEE Signal Processing - July 2018 - 67
IEEE Signal Processing - July 2018 - 68
IEEE Signal Processing - July 2018 - 69
IEEE Signal Processing - July 2018 - 70
IEEE Signal Processing - July 2018 - 71
IEEE Signal Processing - July 2018 - 72
IEEE Signal Processing - July 2018 - 73
IEEE Signal Processing - July 2018 - 74
IEEE Signal Processing - July 2018 - 75
IEEE Signal Processing - July 2018 - 76
IEEE Signal Processing - July 2018 - 77
IEEE Signal Processing - July 2018 - 78
IEEE Signal Processing - July 2018 - 79
IEEE Signal Processing - July 2018 - 80
IEEE Signal Processing - July 2018 - 81
IEEE Signal Processing - July 2018 - 82
IEEE Signal Processing - July 2018 - 83
IEEE Signal Processing - July 2018 - 84
IEEE Signal Processing - July 2018 - 85
IEEE Signal Processing - July 2018 - 86
IEEE Signal Processing - July 2018 - 87
IEEE Signal Processing - July 2018 - 88
IEEE Signal Processing - July 2018 - 89
IEEE Signal Processing - July 2018 - 90
IEEE Signal Processing - July 2018 - 91
IEEE Signal Processing - July 2018 - 92
IEEE Signal Processing - July 2018 - 93
IEEE Signal Processing - July 2018 - 94
IEEE Signal Processing - July 2018 - 95
IEEE Signal Processing - July 2018 - 96
IEEE Signal Processing - July 2018 - 97
IEEE Signal Processing - July 2018 - 98
IEEE Signal Processing - July 2018 - 99
IEEE Signal Processing - July 2018 - 100
IEEE Signal Processing - July 2018 - 101
IEEE Signal Processing - July 2018 - 102
IEEE Signal Processing - July 2018 - 103
IEEE Signal Processing - July 2018 - 104
IEEE Signal Processing - July 2018 - 105
IEEE Signal Processing - July 2018 - 106
IEEE Signal Processing - July 2018 - 107
IEEE Signal Processing - July 2018 - 108
IEEE Signal Processing - July 2018 - 109
IEEE Signal Processing - July 2018 - 110
IEEE Signal Processing - July 2018 - 111
IEEE Signal Processing - July 2018 - 112
IEEE Signal Processing - July 2018 - 113
IEEE Signal Processing - July 2018 - 114
IEEE Signal Processing - July 2018 - 115
IEEE Signal Processing - July 2018 - 116
IEEE Signal Processing - July 2018 - 117
IEEE Signal Processing - July 2018 - 118
IEEE Signal Processing - July 2018 - 119
IEEE Signal Processing - July 2018 - 120
IEEE Signal Processing - July 2018 - 121
IEEE Signal Processing - July 2018 - 122
IEEE Signal Processing - July 2018 - 123
IEEE Signal Processing - July 2018 - 124
IEEE Signal Processing - July 2018 - 125
IEEE Signal Processing - July 2018 - 126
IEEE Signal Processing - July 2018 - 127
IEEE Signal Processing - July 2018 - 128
IEEE Signal Processing - July 2018 - 129
IEEE Signal Processing - July 2018 - 130
IEEE Signal Processing - July 2018 - 131
IEEE Signal Processing - July 2018 - 132
IEEE Signal Processing - July 2018 - 133
IEEE Signal Processing - July 2018 - 134
IEEE Signal Processing - July 2018 - 135
IEEE Signal Processing - July 2018 - 136
IEEE Signal Processing - July 2018 - 137
IEEE Signal Processing - July 2018 - 138
IEEE Signal Processing - July 2018 - 139
IEEE Signal Processing - July 2018 - 140
IEEE Signal Processing - July 2018 - Cover3
IEEE Signal Processing - July 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com