  In this work, we study the online robust principal components' analysis
(RPCA) problem. In recent work, RPCA has been defined as a problem of
separating a low-rank matrix (true data), $L$, and a sparse matrix (outliers),
$S$, from their sum, $M:=L + S$. A more general version of this problem is to
recover $L$ and $S$ from $M:=L + S + W$ where $W$ is the matrix of unstructured
small noise/corruptions. An important application where this problem occurs is
in video analytics in trying to separate sparse foregrounds (e.g., moving
objects) from slowly changing backgrounds. While there has been a large amount
of recent work on solutions and guarantees for the batch RPCA problem, the
online problem is largely open."Online" RPCA is the problem of doing the above
on-the-fly with the extra assumptions that the initial subspace is accurately
known and that the subspace from which $l_t$ is generated changes slowly over
time. We develop and study a novel "online" RPCA algorithm based on the
recently introduced Recursive Projected Compressive Sensing (ReProCS)
framework. Our algorithm improves upon the original ReProCS algorithm and it
also returns even more accurate offline estimates. The key contribution of this
work is a correctness result (complete performance guarantee) for this
algorithm under reasonably mild assumptions. By using extra assumptions --
accurate initial subspace knowledge, slow subspace change, and clustered
eigenvalues -- we are able to remove one important limitation of batch RPCA
results and two key limitations of a recent result for ReProCS for online RPCA.
To our knowledge, this work is among the first few correctness results for
online RPCA. Most earlier results were only partial results, i.e., they
required an assumption on intermediate algorithm estimates.
