IEEE Signal Processing - July 2018 - 48

video analytics application. The incPCP algorithm is an RPLow-rank plus column-sparse interpretation: Outlier pursuit
CA-based solution for video analytics that is online and near
Recall that RSR assumes that an entire data vector is either
real time; it uses extra heuristics to deal
an inlier or an outlier. Borrowing ideas from
with camera jitter and to handle panning
The CDnet 2012 data set is the S+LR literature, one way to reformulate
and camera motion [52]. Grassmannian
the real-world region-level this problem is as follows. The data matrix
online subspace updates with structured
M can be split as M = L + S C, where S C
benchmark obtained by
sparsity (GOSUS) [53] is another increis a column-sparse matrix (many columns
human experts.
mental algorithm that uses structured
are zero and some are nonzero) [58]. With
sparsity of the outlier terms in conjuncthis, an easy extension of the PCP idea can
tion with a GRASTA-like (or an ReProCS-like) algorithm.
solve this problem. This was called outlier pursuit in [58]
Finally, two useful modifications of the ReProCS idea
and solves
exploit the fact that, for many video applications, the foreu * + m Su C 2, 1 subject to M = L
u + Su C .
ground (sparse outlier) support changes in a correlated fashmin L
u , Su
L
ion over time. The first, called modified-ReProCS [12], [18],
simply assumes slow support change of the sparse outliers.
Here, Su 2, 1 is the l 1 norm of the vector of column-wise l 2
Thus, instead of recovering the outlier vector and its support
norms. It is a commonly used convex surrogate for promoting
via l 1 minimization (or CoSaMP, etc.), it uses the modifiedgroup sparsity in the CS literature. The same program was also
proposed in almost parallel work by McCoy and Tropp [31]
CS idea [45]. Modified-CS is designed to exploit partial supwhere it was called low-leverage decomposition. The guaranport knowledge in sparse signal recovery. The estimate of
tee given by Xu et. al [58] for outlier pursuit is given previously
the outlier support from the previous time instant serves as
in Theorem 2.4.
the partial support knowledge. Replacing modified-CS by
weighted-l 1 further helps in certain settings. The supportpredicted modified-ReProCS approach (modified-ReProCS)
Maximizing mean absolute deviation via
[54] generalizes this basic idea further to include a support
mean absolute deviation rounding
prediction step based on a simple object motion model and a
In [31], McCoy and Tropp developed a randomized algorithm
Kalman filter to track the object's motion and velocity. Modicalled MDR to approximate the robust first PC. This is defined
fied-ReProCS [12] is a truly practically useful algorithm since
as v MDR := max v: v = 1 M l v 1 := max || v: | | = 1 R i vl m i . This
it can be used without any assumptions on how many movcost is called MAD and is a classical metric for robust estimaing objects, or regions, are there in a video; it only assumes
tion known since the work of Huber going back to the 1980s.
that the foreground support does not change drastically. Its
The later PCs can be computed by projecting the data vectors
practical version uses a simple heuristic to decide when to use
orthogonal to the subspace spanned by the previous ones (the
modified-CS and when to stick with simple l 1 minimization.
projection pursuit PCA idea of Huber). The MDR solution is a
computationally efficient algorithm to approximate v MDR . It
We compare it in Table 3.
first solves a semidefinite programming (SDP) relaxation of the
original maximizing MAD problem. The SDP can be solved in
Robust subspace recovery
polynomial time, whereas the original problem is nonconvex.
Next, it uses the output of the SDP in a randomization proceHistory
dure to generate K candidate guesses of v MDR . The algorithm
The robustness of PCA methods was first addressed in the
fields of statistics and neural networks. In the statistics literathen picks the "best" one (the one that maximizes the MAD)
ture in 1980s, the predominant approach consists in replacing
and outputs that as an estimate of v MDR . The authors show that
the standard estimation of the covariance matrix with a robust
the MDR algorithm is guaranteed to provide an estimate of
estimator of the covariance matrix [55], [56]. This formulation
the first robust PC whose MAD is at least (1 - e) times that
weights the mean and the outer products that form the covariof v MDR with high probability The probability is high enough
ance matrix. Calculating the eigenvalues and eigenvectors of
when K is large enough.
this robust covariance matrix gives eigenvalues that are robust
to sample outliers. The result is more robust but unfortunateOutlier-robust principal component analysis [32]
ly is limited to relatively low-dimensional data. The second
Given a mix of authentic and corrupted points, Xu et al. [32]
approach to RPCA uses this idea along with projection purproposed the high-dimensional RPCA (HR-PCA) approach.
suit techniques [57]. In the old neural network literature in the
This attempts to find a low-dimensional subspace that cap1990s, Xu and Yuille [1] first addressed the problem of RPCA
tures as much variance of the authentic points as possible. As
by designing a neural network that relied on self-organizing
explained in [32], HR-PCA alternates between a PCA and a
rules based on statistical physics. The PCA energy function
"random removal" step in each iteration. For the PCA step,
proposed by Oja was generalized by adding a binary decision
a candidate subspace is found via PCA on the "clean points"
field with a given prior distribution to take into account the
identified by the previous iteration. Its quality is measured
outliers. The binary variables are zero when a data sample is
by computing its trimmed variance (TV) which is defined
2
considered an outlier.
as TV (Pt ) := R rj = 1 R rk = 1 (Pt ) jl m (k) r . Here (Pt ) lj m (k) is the
48

IEEE Signal Processing Magazine

July 2018

Table of Contents for the Digital Edition of IEEE Signal Processing - July 2018