IEEE Signal Processing - July 2018 - 35

This application is best solved using tensors rather than matrices; however, to explain the idea, we will just use the simpler
matrix formulation. In this case, , t is the vector (or tensor) of
network link "strengths" at time t when no anomalous behavior
is present while st is the vector (or tensor) of outlier entries [24].
Outliers occur due to occasional anomalous behavior or due to
node failures on a few edges. Hence, they are well modeled as
being sparse.

Recommendation system design
The recommendation system design actually requires solving the
RMC problem. To understand the problem, consider a specific
example, say, the Netflix problem, which involves designing a
movie recommendation system. Suppose there are n movies and
d users. We use , t to denote the vector of true movie preferences of user t. The vector st would contain the outlier entries
(if any). The matrix L is well modeled as being low rank under
the assumption that user preferences are governed by only a few
factors, rL . The outliers st occur because some users enter some
incorrect ratings due to laziness, malicious intent, or just typographical errors [4]. These are clearly sparse. The data matrix
M := L + S is also incomplete since any given user does not rate
all movies. The goal in this case is to complete the true movie
preferences' matrix L while being robust to the outliers. This is
then used to recommend movies to the users.

Survey data analysis
A related application is in survey data analysis. Consider a
survey with n questions given to d participants. If all participants answer questions truthfully and carefully (no malicious
or typographical errors), then the survey answers of the tth

participant form , t . This is a valid model under the assumption that the responses to all survey questions are governed
by many fewer factors than n or d, and, hence, the resulting
matrix formed by the true survey responses is low rank. The
goal of the survey is, in fact, to find these few factors (PCs
of this matrix). The problem becomes one of RPCA because
some of the participants' entries will be wrong due to mistakes
and typos. These are modeled as the sparse corruptions st . If
the entries are wrong due to malicious participants, then the
column-sparse model is a more appropriate one.

Desirable algorithm properties
In terms of algorithm design, the following are important questions to ask.
■ Provably correct and under what assumptions. It is useful
to know if an algorithm is guaranteed to be correct under
simple and practically valid assumptions. We say that a
guarantee is a complete correctness result or complete
guarantee if it makes assumptions only on the algorithm
input (the input data, parameters, and the initialization, if
any) and proves that the algorithm output is within a small
error of the true value of the quantity of interest. In all
other situations, we say that the guarantee is a partial guarantee. This could mean many things: it could mean that the
result makes assumptions on intermediate algorithm estimates; or that the guarantee only proves that the algorithm
converges to a local minimum (or just to some stationary
point) of a cost function. A partial guarantee by itself is
usually not very useful. However, sometimes the proof
technique used for obtaining it may be useful and may help
obtain a complete correctness result in later work.

Denoising a Very Noisy Video. PSNR Shown in Parenthesis

Original

Noisy

RPCA-VBM3D
VBM3D
(PSNR = 30 dB) (PSNR = 25 dB)

Video Enhancement: "Seeing" in the Dark

Original

RPCA

(a)

Hist-Eq

(b)

Figure 3. RPCA to enable video enhancement and denoising [12], [25]. (a) Denoising a very noisy video [video with Gaussian noise of standard deviation
v = 70 and hence peak signal-to-noise ratio (PSNR) 11 dB]: we show original and noisy videos in first two columns. The noisy video had PSNR 11 dB.
RPCA-VM3D uses an RPCA algorithm (ReProCS) to first separate it into sparse and low-rank layers, and then apply the best denoiser from literature,
VBM3D, on each layer. The last column directly applies VBM3D to the video. Notice that this gives a much more blurred denoised image. PSNR is noted
below each figure too. (b) Video enhancement via RPCA: an application where an RPCA algorithm (ReProCS) helps to "see" in the dark. A standard
approach for such low-light data is to do contrast enhancement using histogram equalization. As can be seen from the third column (Hist-Eq), this fails.
The code for this experiment is downloadable from http://www.ece.iastate.edu/~hanguo/ReLD_Denoising.zip.

IEEE Signal Processing Magazine

July 2018

http://www.ece.iastate.edu/~hanguo/ReLD_Denoising.zip

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