Robust Pr incipal Component Analysis? 11:7
particular, the clever golfing scheme [Gross 2011] plays a crucial role in our analysis,
and we introduce t wo novel modifications to this scheme.
Despite these similarities, our ideas depart from the literature on matrix completion
on several fronts. First, our results obviously are of a different nature. Second, we
could think of our separation problem, and the recovery of the low-rank component, as
amatrixcompletionproblem.Indeed,insteadofhavingafractionofobservedentries
available and the other missing, we have a fraction available, but do not know which
one, while the other is not missing but entirely corrupted altogether. Although, this
is a harder problem, one way to think of our algorithm is that it simultaneously de-
tects the corrupted entries, and perfectly fits the low-rank component to t he remaining
entries that are deemed reliable. In this sense, our methodology and results go be-
yond matrix completion. Third, we i ntroduce a novel derandomization argument that
allows us to fix the signs of the nonzero entries of the sparse component. We believe
that this technique will have many applications. One such application is in the area
of compressive sensing, where assumptions about the randomness of the signs of a
signal are common, and merely made out of convenience rather than necessity; this is
important because assuming independent signal signs may not make much sense for
many practical applications when the involved signals can all be nonnegative (such as
images).
We mentioned earlier the related work [Chandrasekaran et al. 2009], which also
considers the problem of decomposing a given data matrix into sparse and low-rank
components, and gives sufficient conditions for convex programming to succeed. These
conditions are phrased in terms of two quantities. The first is the maximum ratio
between the !
∞
norm and the operator norm, restricted to the subspace generated
by matrices whose row or column spaces agree with those of L
0
.Thesecondisthe
maximum ratio between the operator norm and the !
∞
norm, restricted to the subspace
of matrices that vanish off the support of S
0
.Chandrasekaranetal.[2009]showthat
when the product of t hese two quantities is small, then the recovery is exact for a
certain interval of the regularization parameter.
One very appealing aspect of this condition is that it is completely deterministic: it
does not depend on any random model for L
0
or S
0
.Ityieldsacorollarythatcanbe
easily compared to our result: suppose n
1
= n
2
= n for simplicity, and let µ
0
be the
smallest quantity satisfying (1.2), then correct recovery occurs whenever
max
j
{i :[S
0
]
ij
)= 0}×
&
µ
0
r/n < 1/12.
The left-hand side is at least as large as ρ
s
√
µ
0
nr ,whereρ
s
is the fraction of entries
of S
0
that are nonzero. Since µ
0
≥ 1always,thisstatementonlyguaranteesrecovery
if ρ
s
= O((nr )
−1/2
); that is, even when rank(L
0
) = O(1), only vanishing fractions of the
entries in S
0
can be nonzero.
In contrast, our result shows that for incoherent L
0
,correctrecoveryoccurswith
high probability for rank(L
0
)ontheorderofn/[µ log
2
n]andanumberofnonzero
entries in S
0
on the order of n
2
.Thatis,matricesoflargerankcanberecoveredfrom
non-vanishing fractions of sparse errors. This improvement comes at the expense of
introducing one piece of randomness: a uniform model on the error support.
AdifferencewiththeresultsinChandrasekaranetal.[2009]isthatouranalysis
leads to the conclusion that a single universal value of λ,namelyλ = 1/
√
n,workswith
high probability for recovering any low-rank, incoherent matrix. In Chandrasekaran
et al. [2009], the parameter λ is data-dependent, and may have to be selected by solving
anumberofconvexprograms.ThedistinctionbetweenourresultsandChandrasekaran
et al. [2009] is a consequence of differing assumptions about the origin of the data
matrix M.Weregardtheuniversalityofλ in our analysis as an advantage, since it may
Journal of the ACM, Vol. 58, No. 3, Article 11, Publication date: May 2011.