IEEE Signal Processing - July 2018 - 38

Table 1. Comparing assumptions, time, and memory complexity for RPCA solutions. For simplicity, we ignore all dependence on condition numbers.
All the algorithms require left and right incoherence, and thus we do not list this in the third column.
Algorithm

Outlier Tolerance, Rank of (L)

Assumptions

Memory, Time,

# of Parameters

PCP(C) [4] (offline)

max-outlier-frac-row = O ^1 h
max- outlier-frac- col = O ^1 h
c min ^n, d h
rL #
log 2 n

Uniform random outlier
support

Mem: O ^nd h

Zero

AltProj [8] (offline)

Time: O c nd 2 1 m
e

max - outlier - frac - row = O ^1/rL h

Mem: O ^nd h

max -outlier -frac-col = O ^1/rL h

RPCA-GD [10] (offline)

max -outlier -frac- row =
max -outlier -frac -col =

PG-RMC [17] (offline)

Mem: O ^nd h

O ^1/r 1L .5h

max -outlier -frac-row = O ^1/rL h
max -outlier -frac-col = O ^1/rL h

ReProCS-NORST
[27], [28] (online)
detects and tracks
subspace change

Time:

O ^1/r 1L .5h

max -outlier -frac -row = O ^1 h
max -outlier -frac -col = O ^1/rL h

O c ndr 2L log

Two
1m
e

Five

Time: O c ndrL log 1 m
Mem: O ^nd h

d.n

Time:
Outlier magnitude lower
bounded slow subspace
change or fixed subspace
first Cr samples: AltProj
assumptions

e

Four

O c nr 3L log 2 n log 2

1m
e

Four

Mem: O c nrL log n log 1 m
e

Time: O c ndrL log 1 m
e

Track delay: O c r log n log 1 m
e

We compare the theoretical guarantees for these solutions in
Tables 1 and 2 and experimental performance (for video analytics) in Table 3. As can be seen, among the provable solutions, ReProCS has the best experimental performance and is
the fastest. AltProj is about three times slower. GD and NORMC are, in fact, slower than AltProj.

4) subspace change: let T : = max j SE (Pj - 1, Pj)
a) t j + 1 - t j 2 Cr log n log (1/e)
b) T # 0.8 and C 1 rm + (T + 2e) # s min
5) init: SE (Pt 0, P0) # 0.25, C 1 rm + SE (Pt 0, P0) # s min
6) algorithm parameters are appropriately set; then, with
probability (w.p.) $ 1 - 10dn -10, SE (Pt (t), P(t)) #

Robust subspace tracking: A summary
In [7], [9], [12], [27], and [29], the novel online solution framework ReProCS was introduced to solve the RST or the dynamic RPCA problem. The best ReProCS guarantee is given next.
This is for a ReProCS-based algorithm that we call ReProCSNORST because its tracking delay is nearly optimal [27], [28].
At each time, it outputs Pt (t), ,tt, ts t, Tt t. It also outputs ttj as the
time at which it detects the jth subspace change.

Theorem 2.3 (Recursive projected compressive
sensing-nearly optimal robust subspace tracking
guarantee for robust subspace tracking)

Let a : = Cr log n, K : = E [a 1 a 1l ], and m + : = m max (K),
m : = m min (K), and let s min : = min t min i ! Tt (s t) i denote the
m i n i mu m out l ier mag n it ude. P ick a n e # min (0.01,
0.4 min j SE (Pj - 1, Pj) 2 f ) . If
1) Pj s are μ-incoherent; and a t s are zero mean, mutually
independent over time t, have identical covariance matrices, i.e., E [a t a tl ] = K, are element-wise uncorrelated (K
is diagonal), are element-wise bounded (for a numerical
constant h, (a t) 2i # hm i (K)), and are independent of all
outlier supports T t
2
2) w t # cr E [w t wlt] , E [w t wlt] # ce 2 m -, zero mean,
mutually independent, independent of s t, , t
3) max-outlier-frac-col # c 1 nr, max-outlier-frac-row a # c 2
38

if t ! [t j, t j + a),
(e + T)
k-1
0
3
(
.
)
(
)
e + T if t ! [t j + (k - 1) a, t j + ka),
*
if t ! [t j + Ka + a, t j + 1),
e
where K := C log (1/e). Memory complexity is O (nr log n
log (1/e)) and time complexity is O (ndr log (1/e)).
In the statement of Theorem 2.3, the condition number,
f : = m + /m - is treated as a numerical constant and ignored.
Under the assumptions of the theorem, the following also hold:
1) st t - s t = ,tt - , t # 1.2 (SE (Pt (t), P(t)) + e) , t
2) at all times, t, Tt t = T t
3) t j # ttj # t j + 2a
s off
4) O f f l i n e - N O R S T : SE (Pt (off
t) , P(t)) # e, t
t - st =
off
,tt - , t # e , t at all t.
Observe that ReProCS-NORST can automatically detect
and track subspace changes with delay that is only slightly
more than r (near optimal). Also, its memory complexity is within log factors of nr (memory needed to output
the subspace estimate). The second key point is that, after
the first Cr data samples (used for initialization) for a-sample
mini-batches of data, it tolerates a constant maximum fraction of outliers per row without any assumption on outlier
support. This is possible because it makes two other extra
assumptions: fixed or slow subspace change and a lower
bound on s min (see last two assumptions of Theorem 2.3).

IEEE Signal Processing Magazine

|

July 2018

|



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