IEEE Signal Processing - July 2018 - 33

or in rating movies. For this problem setting,
accomplished via SVD on the data matrix.
This article provides
it is clearly impossible to recover the entire
The same problem becomes much harder if
a magazine-style
low-rank matrix L; it is only possible to
the data is corrupted by even a few outliers.
overview of the entire
The reason is that SVD is sensitive to outlicorrectly estimate its column subspace (and
field of rSL and tracking.
ers. We show an example of this in Figure 1.
not the individual PCs). In modern literaIn today's big data age, since data is often
ture, this problem is referred to as RSR [13].
acquired using a large number of inexpensive sensors, outliers
Henceforth, the terms RPCA and RST refer only to the
are becoming even more common. They occur due to variS+LR definitions while RSR is the aforementioned probous reasons such as node or sensor failures, foreground occlulem. See [14] for a detailed review of RPCA and RST via
sion of video sequences, or abnormalities or other anomalous
S+LR, and [15] for a review of RSR.
behavior on certain nodes of a network. The harder problem of
Two important extensions of RPCA are
PCA or subspace learning for outlier corrupted data is called
■ robust matrix completion (RMC) (or RPCA with missing
RPCA or RSL.
data or low-rank matrix completion with sparse outliers)
Since the term outlier does not have a precise mathemati[16], [17]
cal meaning, the RPCA problem was, until recently, not well
■ compressive or undersampled RPCA that involves
defined. Even so, many classical heuristics existed for solving
RPCA from undersampled projected linear measureit, e.g., see [1] and [2] and references therein. In recent years,
ments [18]-[22].
there have been multiple attempts to qualify this term. Most
This is useful in dynamic or functional magnetic resonance
popular among these is the idea of treating an outlier as
imaging (MRI) applications.
an additive sparse corruption, which was popularized in the
work of Wright and Ma [3]. This is a valid definition because
Applications
it models the fact that outliers occur infrequently and allows
We describe some of the modern applications where the RPCA
them to have any magnitude. In particular, their magnitude
problem occurs.
can be much larger than that of the true data points. Using this
definition, the recent work by Candès et al. [4] defined RPCA
Computer vision and video analytics
as the problem of decomposing a given data matrix, M, into
A large class of videos, e.g., surveillance videos, consists of
the sum of a low-rank matrix, L, whose column subspace
a sparse foreground layer that contains one or more moving
gives the PCs and a sparse matrix (outliers' matrix), S. This
definition, which is often referred to as the S+LR formulaSVD on Data Corrupted by
tion, has led to numerous interesting new works on RPCA
Small Noise Finds the Correct PC
solutions, many of which are provably correct under simple
assumptions, e.g., [4]-[10]. A key motivating application is
20
video analytics: decomposing a video into a slowly changing
background video and a sparse foreground video [2], [4]; see
an example in Figure 2(a). The background changes slowly,
0
and the changes are usually dense (not sparse). It is thus well
modeled as a dense vector that lies in the low-dimensional
subspace of the original space [4]. The foreground usually
−20
consists of one or more moving objects, and is thus correctly
−10
−5
0
5
10
modeled as the sparse outlier.
(a)
Often, for long data sequences, e.g., long surveillance vidSVD on Outlier-Corrupted
eos, or long dynamic social network connectivity data sequencData Provides a Wrong Estimate of the PC
es, if one tries to use a single lower-dimensional subspace to
represent the data, the required subspace dimension may end
20
up being quite large. For such data, a better model is to assume
that it lies in a low-dimensional subspace that can change over
time, albeit gradually. The problem of tracking a (slowly)
0
changing subspace over time is often referred to as subspace
tracking or dynamic PCA. The problem of tracking it in the
presence of additive sparse outliers can thus be called either
−20
5
10
−10
−5
0
RST or dynamic RPCA [7], [11], [12].
(b)
Another way to interpret the word outlier is to assume that
either an entire data vector is an outlier or it is an inlier. This a
Figure 1. (a) PCA in small noise: the SVD solution works. The black line
more appropriate model for outliers due to malicious users in
is the estimated PC computed using the observed data. (b) PCA in outlirecommendation system design or due to malicious participants
ers: the SVD solution fails to correctly find the direction of largest variin survey data analysis who enter all wrong answers in a survey
ance of the true data. Instead its estimate is quite far from the true PC.
IEEE SIgnal ProcESSIng MagazInE

July 2018

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