In this work we develop and study a novel online robust principal components’ analysis (RPCA) algorithm based on the recently introduced ReProCS framework. Our algorithm significantly 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 for this algorithm under relatively mild assumptions. By using extra (but usually valid) assumptions we are able to remove one important limitation of batch RPCA results and two important limitations of a recent result for ReProCS for online RPCA. To the best of our knowledge, this work is among the first correctness results for online RPCA.

We study the problem of sequentially recovering a sparse vector xtand a vector from a low-dimensional subspace ℓtfrom knowledge of their sum mt= xt+ ℓt. If the primary goal is to recover the low-dimensional subspace where the ℓt's lie, then the problem is one of online or recursive robust principal components analysis (PCA). To the best of our knowledge, this is the first correctness result for this problem. We prove that if a good estimate of the initial subspace is available; the ℓt's obey certain denseness and slow subspace change assumptions; and the support of xtchanges either at every frame or at least every so often, then with high probability, the support of xtwill be recovered exactly, and the error made in estimating xtand ℓtwill be small. An example where this problem occurs is in separating a sparse foreground and a slowly changing dense background from surveillance videos.

“To be considered for an 2015 IEEE Jack Keil Wolf ISIT Student Paper Award.” This work studies two interrelated problems - online robust PCA (RPCA) and online matrix completion (MC). Both problems assume that an accurate estimate of the low-dimensional subspace from which the first true data vector is generated is available. We develop a practical modification of a recently proposed algorithm to solve both problems; and we obtain correctness results for the proposed algorithms under mild assumptions.

This paper studies the recursive robust principal components analysis problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low-dimensional subspace that is either fixed or changes slowly enough. A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above problem, in recent work, we introduced a novel solution called recursive projected CS (ReProCS). In this paper, we develop a simple modification of the original ReProCS idea and analyze it. This modification assumes knowledge of a subspace change model on the Lt's. Under mild assumptions and a denseness assumption on the unestimated part of the subspace of Lt at various times, we show that, with high probability, the proposed approach can exactly recover the support set of St at all times, and the reconstruction errors of both St and Lt are upper bounded by a time-invariant and small value. In simulation experiments, we observe that the last assumption holds as long as there is some support change of St every few frames.