Online Robust PCA or Online Sparse + Low-Rank Matrix Recovery

This work studies the problem of sequentially recovering a time sequence of sparse vectors x_t and vectors from a low-dimensional subspace l_t from knowledge of their sum m_t:=x_t+l_t at each time t. The subspace of l_t's changes slowly enough so that the matrix L_t:= [l_1, l_2, ... l_t] is low-rank at each time t. Clearly the matrix X_t:=[x_1, x_2, ... x_t] is sparse. Thus this is a problem of online sparse + low-rank matrix recovery from their sum. If the primary goal is to recover the low-dimensional subspace in which the l_t's lie, then the problem is one of online 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. In our work, we have developed a novel algorithm called ReProCS to solve this problem and demonstrated its significant advantage over other robust PCA based methods for the video layering problem.
While there has been a large amount of recent work on performance guarantees for the batch robust PCA problem, the online problem is largely open. In recent work, we have shown that, with ReProCS, under mild assumptions and with high probability, the error in recovering the subspace in which l_t lies decays to a small value within a short delay of a subspace change time and the support of x_t is recovered exactly. Moreover, the error made in estimating x_t and l_t is small at all times. The assumptions that we need are (a) a good estimate of the initial subspace is available (easy to obtain using a short sequence of background-only frames in video surveillance); (b) the l_t's obey a `slow subspace change' assumption; (c) the basis vectors for the subspace from which l_t is generated are dense (non-sparse); and (d) the support of x_t changes by at least a certain amount at least every so often.