IEEE Signal Processing - July 2018 - 43

square. For solving RPCA, it deliberately undersamples the
by thresholding out the very large entries of the data matrix
available full matrix M to speed up the algorithm. This algoM to return the first estimate of the sparse matrix. Thus,
t
rithm
is called NO-RMC.
S 0 = HT (M; g 0), where HT denotes the hard thresholdProjected GD is natural heuristic for using GD to solve coning operator and g 0 denotes the threshold used for it. After
strained optimization problems. To solve
this, it computes the residual M - St 0 and
projects it onto the space of rank-1 matrimin x ! C f (x), after each GD step, it projects
AltProj works by projecting the output onto the set C before moving on
ces. Thus, Lt 1 = P1 (M - St 0), where P1
the residual at each step
denotes a projection onto the space of rankto the next iteration.
1 matrices. It then computes the residual
onto the space of either
M - Lt 1 and projects it again onto the space
Robust principal component analysissparse matrices or
of sparse matrices but using a carefully
gradient descent [10]
onto the space of lowselected threshold g 1 that is smaller than
Notice that the matrix L can be decomrank matrices.
t 1; g 1). This prou u l , where Uu is an n # r
posed as L = UV
g 0 . Thus, St 1 = HT (M - L
cess is repeated until a halting criterion is
matrix and Vu is a d # r matrix. The algoreached. The algorithm then moves on to stage two. This stage
rithm alternately solves for S, Uu , Vu . Like AltProj, it also begins
proceeds similarly, but each low-rank projection is now onto
by first estimating the sparse component St 0 . Instead of hard
the space of rank rt = 2 matrices. This process is repeated for
thresholding, it uses a more complicated approach called maxsorting-thresholding for doing this. It then initializes Uut 0 and
r stages.
Vut 0 via r-SVD on M - St 0 followed by "projecting onto the set
of incoherent matrices" (we explain this in the next paragraph).
Why this works
After this, it repeats the following three steps at each iteration:
Once the largest outliers are removed, it is expected that pro1) use "max-sorting-thresholding" applied to M - Lt i - 1 to obtain
jecting onto the space of rank-1 matrices returns a reasonable
rank-1 approximation of L, Lt 1 . This means that the residual
St i; 2a) implement one GD step for minimizing the cost funcu u l + S - M 2F + 0.25 Uu l Uu - Vu l Vu F
tion L (Uu , Vu , S) : = UV
M - Lt 1 is a better estimate of S than M. Because of this, it
can be shown that St 1 is a better estimate of S than St 0 and so
over Uu while keeping Vu , S fixed at their previous values, and
the residual M - St 1 is a better estimate of L than M - St 0 .
2b) obtain Uut i by "projecting the output of step 2a onto the set of
This, in turn, means Lt 2 will be a better estimate of L than Lt 1 .
incoherent matrices"; and 3) obtain Vut i in an analogous fashion.
The proof that the initial estimate of L is good enough relies
The step "projecting onto the set of incoherent matrices"
involves the following. Recall that incoherence (denseness) of
on incoherence of left and right singular vectors of L and the
left and right singular vectors is needed for the static RPCA
fact that no row or column has too many outliers. These two
solutions to work. To ensure that the estimate of Uu after one
facts are also needed to show that each new estimate is better
than the previous.
step of GD satisfies this, RPCA-GD projects the matrix onto
the "space of incoherent matrices." This is achieved by clipping: if a certain row has norm larger than 2nr/n Uut 0 2, then
Time and memory complexity
2
each entry of that row is rescaled so that the row norm equals
The time complexity of AltProj is O (ndr log (1/e)). It operthis value.
ates on the entire matrix, so memory complexity is O (nd).

Nonconvex solutions: Projected gradient descent (Robust
principal component analysis-gradient descent and nearly
optimal-robust matrix completion)
While the time complexity of AltProj was lower than that
of PCP, there was still scope for improvement in speed. In
particular, the outer loop of AltProj that runs r times seems
unnecessary (or can be made to run fewer times). Two more
recent works [10], [17] try to address this issue. The question
asked in [10] was can one solve RPCA with computational
complexity that is of the same order as a single r-SVD? This
has complexity O (ndr (- log e)). The authors of [10] show that
this is indeed possible with an extra factor of l 2 in the complexity and with a tighter bound on outlier fractions. Here, l
is the condition number of L. To achieve this, they developed
an algorithm that relies on projected GD called RPCA-GD.
The authors of [17] use a different approach. They develop a
projected GD solution for RMC and argue that, even in the
absence of missing entries, the same algorithm provides a
very fast solution to RPCA as long as the data matrix is nearly

Nearly optimal-robust matrix completion [17]
The NO-RMC algorithm is designed to solve the more general
RMC problem. Let X denote the set of observed entries, and
let P X denote projection onto a subspace formed by matrices
supported on X . Thus, P X (A) zeroes out entries of A whose
indices are not in X and keeps other entries the same. The
set X is generated uniformly at random. NO-RMC modifies
AltProj as follows. First, instead of running the algorithm in r
stages, it reduces the number of stages needed. In the qth outer
loop, it projects onto the space of rank k q matrices (instead of
rank q matrices in case of AltProj). The second change is in
t which now also includes a GD step before
the update step of L,
the projection. Thus, the ith iteration of the qth outer loop now
computes Lt i = Pk q (Lt i - 1 + (1/p) PX (M - Lt i - 1 - St i - 1)). On
first glance, the projection onto the space of rank k q matrices
should need O (ndk q) time. However, as the authors explain,
because the matrix that is being projected is a sum of a low-rank
matrix and a matrix with many zeroes (sparse matrix as used
in fast matrix algorithms' terminology), the computational cost

IEEE Signal Processing Magazine

July 2018

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