IEEE Signal Processing - July 2018 - 46
recovery is needed to ensure that the subspace estimate can be
improved with each update. This step also requires elementwise boundedness of the a ts along with mutual independence
and identical covariances (these together are similar to right
incoherence of L; see [27]).
Remark 3.5 (Relax outlier magnitudes lower bond assumption)
The outlier magnitudes, lower bound assumption of the
ReProCS-NORST theorem given in the "An Overview" section can be relaxed to lower bound on most outlier magnitudes.
In particular, the following suffices: assume that s t can be
split into s t = (s t) small + (s t) large that are such that, in the kth
subspace update interval, (s t) small # 0.3 k - 1 (e + T) rm +
and the smallest nonzero entry of (s t) large is larger than
C0.3 k - 1 (e + T) rm + .
If there were a way to bound the element-wise error of the
CS step (instead of the l 2 norm error), the above requirement
could be relaxed further.
Relating projected compressive sensing
and robust regression
Projected CS is equivalent to solving the robust regression problem with a sparsity model on the outliers. To understand this
simply, let Pt = Pt(t - 1) . The exact version of robust regression ast t + s t, while its approxisumes that the data vector m t equals Pa
mate version assumes that this is only approximately true. Since
Pt is only an approximation to P(t), even in the absence of unstructured noise w t, approximate robust regression is the correct problem to solve for our setting. Its unconstrained version involves
t - s 2 . Observe that one can solve for
min a, s m s 1 + m t - Pa
a in closed form to get at = Pt l (m t - s). Substituting this, the
t t l ) (m t - s) 2 .
minimization simplifies to min s s 1 + (I - PP
This is exactly the same as the Lagrangian version of projected CS. The version for which we obtain guarantees solves
t t l ) (m t - s) 2 # p 2, but we could also
min s s 1 s.t. (I - PP
have used other CS results and obtained guarantees for the Lagrangian version with minimal changes.
Online solution 2: Modified-principal component pursuit
for robust principal component analysis with partial
subspace knowledge and for dynamic robust principal
component analysis
A simple extension of PCP, called modified-PCP, provides a
nice solution to the problem of RPCA with partial subspace
knowledge [30]. This problem often occurs in face recognitiontype applications: the training data set may be outlier-free, but,
due to limited training data, it may not contain all possible
directions of variation of the face subspace. To understand the
solution idea, let G denote the basis matrix for the partial subspace knowledge. If G is such that the matrix (I - GGl ) L has
rank smaller than rL, then the following is a better idea:
u
min Lu , Su (I - GGl ) L
*
+ m Su
1
u + Su = M.
subject to L
This solution was called modified-PCP because it was
inspired by a similar idea, called modified-CS [45], that solves
46
the problem of CS (or sparse recovery) when partial support
knowledge is available. More generally, even if the approximate rank of (I - GGl ) L is much smaller, i.e., suppose that
L = GA + W + L new, where L new has ran k rnew % rL and
W F # e is small, the following simple change to the same
idea works:
u new
min Lu new, Su, Au L
*
+ m Su
1
s.t. M - Su - GAu
F
#e
and output Lt = GAt + Lt new . To solve the tracking problem
using modified-PCP, the subspace estimate from the previous
set of a frames serves as the partial subspace knowledge G for
the current set. It is initialized using PCP.
The modified-PCP guarantee was proved using ideas borrowed from [4] for PCP [PCP(C)]. It shows that, when rnew % r,
modified-PCP needs a much weaker version of the strong
incoherence condition needed by PCP. However, like PCP (and
unlike ReProCS), it also needs uniformly randomly generated
support sets, which is a strong requirement. But, also like PCP
(and unlike ReProCS), it does not need a lower bound on outlier magnitudes. However, its slow subspace change assumption is unrealistic. Also, it does not detect the subspace change
automatically, i.e., it assumes t j is known. This last limitation
can be removed by using the ReProCS approach to detecting
subspace change [9], [29].
Summary discussion of all simple (and provably
correct) approaches
A summary is provided in Table 1. The results for PCP(C) and
modified-PCP both require uniform random support (impractical requirement), but, because of that, both allow a constant
outlier fraction in any row or column of the data matrix. The
PCP(H) result as well as all follow up works (AltProj, ReProCS,
GD, NO-RMC) does not require any outlier support generation
model, but, because of that, they require a tighter bound on the
outlier fractions in any row or column. AltProj and NO-RMC
allow this to be O (1/rL) while GD requires this to be O ^1/r 1L.5 h.
ReProCS has the best outlier fraction tolerance: for the first Cr
frames it needs the fractions to be O (1/r); after that it needs
the fraction in any row of a a sample mini-batch to only be
O (1), while it needs the fraction in any column to be O (1/r).
The row bound is better than the information theoretic upper
bound on what can be tolerated without extra assumptions.
ReProCS uses fixed or slow subspace change and most outlier
magnitudes lower bounded to obtain this advantage. These two
extra assumptions (and a different way to ensure right incoherence) also help get an online algorithm that has near-optimal
memory complexity and near-optimal tracking delay.
In terms of time complexity, PCP is the slowest because it
needs to solve a convex program; AltProj is much faster. GD
and ReProCS are faster than AltProj, and NO-RMC is the fastest. Up to log factors, its time complexity is order nr 2L . For
small rL, this is almost linear in the number of unknowns.
However, to achieve this, it deliberately undersamples the full
data matrix and then solves an RMC problem; and for this to
work correctly, it requires the data matrix to be nearly square.
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