IEEE Signal Processing - July 2018 - 36

Component Analysis and Robust Subspace
Practical accuracy. Performance guarBeing able to correctly
Tracking via Sparse+Low-Rank: Problem
antees are often just sufficient condisolve the video-layering
Setting" and "Robust Subspace Recovery"
tions. Also the assumptions required
problem (separate a
sections, we explain the solution approaches
can be hard to verify in practice. Hence,
video into foreground
in detail. The code for all of the RPCA and
practical accuracy is an equally imporand background layers)
RST solutions is available via the GitHub
tant measure of algorithm success.
enables better solutions
library of Andrew Sobral [26]: https://github
Commonly used metrics for RPCA
.com/andrewssobral/lrslibrary.
include normalized recovery error of L
to many other video
In our guarantees and elsewhere, we use
or the error in recovering its column
analytics and computer
the letters C, c to denote different numerical
span. If the outlier matrix S is the "quanvision applications.
constants in each use. To keep our statements
tity" of interest, e.g., in case of foresimple, condition numbers are treated as
ground object tracking, then the error in
numerical constants (and combined with C or c).
recovering its support is often a more useful metric.
■ Time complexity. Both order-wise computational complexity and actual experimental comparisons of time taken
Robust principal component analysis and robust
are important. The former is useful because it can take too
subspace tracking via sparse+low-rank: Problem setting
long to do experimental comparisons for very large-sized
problems. The latter is useful because order-wise comStatic robust principal component analysis [4]
plexity ignores constants that can sometimes be very large
Given an n # d observed data matrix,
in practice. We discuss both types of time comparisons in
this article.
M := L + S + W,
■ Memor y complexity and/or number of passes. In
where L is a low rank matrix (true data), S is a sparse matrix
today's big data age, this is often the most important
concern. It can be the bottleneck even for applications for
(outlier matrix), and W is small unstructured noise/modeling
which real-time output is not needed and, hence, slow
error, the goal is to estimate L and, hence, its column space.
algorithms can be tolerated. We say that an algorithm is
We use rL to denote the rank of L. The maximum fraction of
memory optimal if it needs the same order of memory as
nonzeros in any row (column) of the outlier matrix S is denoted
the algorithm output. So, for RPCA, an algorithm would
by max-outlier-frac-row (max-outlier-frac-col). The column
be memory optimal if it needed memory of order O (nr).
space of Lt then gives the PCA solution.
It is nearly memory optimal if its memory complexity
is within logarithmic factors of the optimal. If the data
Robust subspace tracking or dynamic robust
set needs to be loaded from a storage device while runprincipal component analysis [7]
ning the algorithm, another related concern is the number
At each time t, we get a data vector m t ! R n that satisfies
of passes required. This number then governs the number
of times the data needs to be reloaded. For processing
m t := , t + s t + w t, for t = 1, 2, f, d,
very large data sets, one needs algorithms that are either
nearly memory optimal or need few passes through the
where w t is small unstructured noise, st is the sparse outlier
data, ideally both.
vector, and , t is the true data vector that lies in a fixed or slowly changing low-dimensional subspace of R n, i.e., , t = P(t) a t,
■ Online (or recursive or causal) versus batch. Online algowhere P(t) is an n # r basis matrix (a matrix with mutually orthorithms are algorithms for settings where inputs or data are
arriving one at a time, and we need to make decisions on
normal columns) with r % n and with (I - P(t - 1) P(t - 1)l ) P(t) ,
the fly or with small delays, without knowing what will
small compared to P(t) = 1. We use Tt to denote the support
happen in the future. In signal processing or controls literaset of st. Given an initial subspace estimate, Pt 0, the goal is to
ture, such an algorithm would be called recursive. The
track span (P(t)) and , t either immediately or within a short
notion of an online algorithm also requires that the algodelay. A by-product is that , t, s t, and Tt can also be tracked
rithm output quality improves as more data come in. For
on the fly. The initial subspace estimate, Pt 0, can be computed
RPCA, this means that the subspace estimate quality
by using only a few iterations of any of the static RPCA soluimproves over time. A batch method, on the other hand,
tions (described next), e.g., PCP [4] or alternating-projection
needs to wait for all data to come in first.
(AltProj) [8], applied to the first t train data samples M [1, t train].
Typically, t train = Cr suffices. Here, [a, b] refers to all integers between a and b, inclusive, [a, b) : = [a, b - 1], and M T
An overview
denotes
a submatrix of M formed by its columns indexed
This section provides an overview of the problem setting
and key solutions for all the three problems discussed in this
by entries in the set T. Alternatively, in some applications,
article along with three sample theoretical guarantees. It is a
e.g., video surveillance, it is valid to assume that outlier-free
quick summary for the reader who is already somewhat famildata are available. In these situations, simple SVD can also
iar with the topic. In the two later sections "Robust Principal
be used.
■

IEEE Signal Processing Magazine

July 2018

https://github.com/andrewssobral/lrslibrary https://github.com/andrewssobral/lrslibrary

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