Online Robust PCA or Online Sparse Matrix Recovery from Large but Structured Noise

This work studies the problem of sequentially recovering a sparse vector x_t and a vector from a low-dimensional subspace l_t from knowledge of their sum m_t=x_t+l_t. If the primary goal is to recover the low-dimensional subspace where the l_t's lie, then the problem is one of online or recursive robust principal components analysis (PCA). An example of where such a problem might arise is in separating a sparse foreground and a slowly changing dense background in a surveillance video. We develop a novel algorithm called ReProCS to solve this problem and demonstrate its significant advantage over other robust PCA based methods for the video analysis problem. 

We prove that if the l_t's obey certain denseness and slow subspace change assumptions, the support of x_t changes by at least a certain amount at least every so often, and some other mild assumptions hold, then with high probability, the support of x_t will be recovered exactly. Also, the error made in estimating x_t and l_t will be small and the subspace recovery error will be decay to a small value within a short delay of a subspace change time. To the best of our knowledge, this is the first complete correctness result for online robust PCA or equivalently for online sparse plus low-rank recovery.