IEEE Signal Processing - July 2018 - 41

ROI tracking [22], both models are equally applicable. For
long videos from static cameras, dynamic is generally a better model to use. The same is true for videos involving slowmoving or occasionally static foreground objects since these
result in a larger fraction of outliers per row of the data matrix.
On the other hand, for videos involving sudden scene changes,
the original RPCA problem is a better fit, since in this case
the slow subspace change assumption absolutely does not hold.
For recommendation system design or survey data analysis, if the initial data set has a certain number of users, but
as time goes on, more users get added to the system, the
following strategy is best. Use a static RPCA solution on the
initial data set. As more users get added, use an RST solution to both update the solution and detect when subspace
changes occur. In both applications, subspace change would
occur when the survey reaches a different previously unrepresented demographic.

function; and/or lower bound some performance metric for the
solution, e.g., explained variance or mean absolute deviation (MAD).

Robust principal component analysis and subspace
tracking via sparse+low-rank matrix decomposition
Understanding identifiability issues

The S+LR formulation by itself does not ensure identifiability. For example, it is impossible to correctly separate M into
L + S if L is also sufficiently sparse in addition to being low
rank or if S is also sufficiently low rank in addition to being
sparse. In particular, there is a problem if S has rank that is
equal to or lower than that of L or if L has support size that is
smaller than or equal to that of S.
For example, if S is sparse with support that never changes
across columns, then S will be a matrix with rank at most s
(where s is the column support size). If, in addition, the nonzero
entries of s t are the same for all t (all columns), then,
Robust subspace recovery: Problem and summary
in
fact,
There is a long body of both old and recent work that studies
S will be a rank-1 matrix. In this case, without extra
the following problem: given a set of d points in R n, suppose
assumptions, there is no way to correctly identify S and L.
that the inlier points lie in an unknown lowThis situation occurs in case of a video with
dimensional subspace, while outlier points
a foreground object that never moves and
Among the provable
are all points that do not. Thus, an entire
whose pixel intensities are such that s t never
solutions, reProCS has
data vector is either an inlier or an outlier.
changes. As a less extreme example, if the
the best experimental
Also suppose that the fraction of outliers is
object remains static for b 0 d frames at a
less than 50% of all data points. Then, how
time before moving, and its pixel intensiperformance and is the
does one find the low-dimensional subspace
ties are such that s t itself is also constant for
fastest. AltProj is about
spanned by the inliers? In recent literature,
these
many frames, then the rank of S will
three times slower. gD and
this body of work has been referred to as
be d/ (b 0 d) = 1/b 0 . If this number is less
NO-rMC are, in fact, slower than rL, then, again, the problem is not idenmean absolute deviation rounding (MDR),
than AltProj.
[31] outlier-RPCA [32], PCA with contamitifiable without extra assumptions. Observe
nated data [33], or, more recently, RSR [13].
that, in this example, max-outlier-frac-row
This is a harder problem to solve especially when the fraction
equals b 0. Thus max-outlier-frac-row needs to be less than 1/rL
of outliers is large since, in this case, entire data vectors get
for identifiability. By a similar argument, max-outlier-frac-col
classified as outliers and are thrown away.
needs the same bound.
While many algorithms have been proposed in recent literThe opposite problem occurs if the left or right singular
ature, complete guarantees under simple assumptions are hard
vectors of L are sparse. If the left singular vectors are sparse,
to obtain. An exception is the outlier pursuit solution [33]. It
L will be a row sparse matrix (some rows will be zero). If
solves this problem by using a nice extension of the PCP idea:
the right singular vectors are sparse, then it will be a column
it models the outliers as additive "column-sparse corruptions."
sparse matrix. If both left and singular vectors are sparse, then
Xu et al. [33] prove the following.
L will be a general S+LR matrix. In all these situations, if
the singular vectors are sparse enough, it can happen that L is
sparser than S, and then it becomes unidentifiable.
Theorem 2.4 (Outlier pursuit guarantee for robust subspace recovery)
It is possible, though, to impose simple assumptions to
c
Let denote the fraction of corrupted columns (outlier fracensure that neither of the aforementioned situations occur. We
tion). Outlier pursuit correctly recovers the column space of L
can ensure that S is not lower rank than L by requiring that
and correctly identifies the outlier support if
the fraction of outliers in each row and each column be at most
c
!
O
(
1
/
r
)
■
L
c/rL with c < 1 [5], [6], [8]. Alternatively, one can assume that
■ the matrix
is column-incoherent, i.e., the row norm of
the matrix of its right singular vectors is bounded by
the outlier support is generated from a uniform distribution;
with this assumption, just a bound on its size suffices [4].
nr ((1 - c) n) .
We can ensure that L is not sparse by requiring that its left
This is a nice and simple correctness guarantee, but it
requires a tight bound on outlier fractions (just like the S+LR
and right singular vectors be dense. This is called the denseliterature). Most other guarantees (described later) only prove
ness or, more generally, the incoherence assumption. The term
asymptotic convergence of the iterates of the algorithm to
incoherence is used to imply that this condition helps ensure
either a stationary point or a local minimum of the chosen cost
that the matrix L is different enough from the sparse matrix
IEEE Signal Processing Magazine

July 2018

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