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

Date
2014-08-01
Authors
Hogben, Leslie
Qiu, Chenlu
Vaswani, Namrata
Lois, Brian
Hogben, Leslie
Vaswani, Namrata
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

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.

Description
<p>This is a manuscript of an article published as Qiu, Chenlu, Namrata Vaswani, Brian Lois, and Leslie Hogben. "Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise." <em>IEEE Transactions on Information Theory</em> 60, no. 8 (2014): 5007-5039. DOI: <a href="http://dx.doi.org/10.1109/TIT.2014.2331344" target="_blank">10.1109/TIT.2014.2331344</a>. Posted with permission.</p>
Keywords
Vectors, Principal component analysis, Robustness, Linear matrix inequalities, Noise, Sparse matrices, Eigenvalues and eigenfunctions
Citation
Collections