Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise

摘要

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, (S_{t}) , in the presence of large but structured noise, (L_{t}) . The structure that we assume on (L_{t}) is that (L_{t}) 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 ( (L_{t}) ) from moving foreground objects ( (S_{t}) ) 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 (L_{t}) 's. Under mild assumptions and a denseness assumption on the unestimated part of the subspace of (L_{t}) at various times, we show that, with high probability, the proposed approach can exactly recover the support set of (S_{t}) at all times, and the reconstruction errors of both (S_{t}) and (L_{t}) 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 (S_{t}) every few frames.