ABSTRACT
This work studies the problem of sequentially recovering a sparse vector St and a vector from a low-dimensional subspace Lt from knowledge of their sum Mt := Lt + St. If the primary goal is to recover the low-dimensional subspace in which the Lt’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. In this chapter, we describe our recently proposed algorithm, called Recursive Projected Compressed Sensing (ReProCS), to solve this problem and demonstrate its significant advantage over other robust PCA-based methods for this
Sparse
video layering problem.We also summarize the performance guarantees for ReProCS. Lastly, we briefly describe our work on modified PCP, which is a piecewise batch approach that removes a key limitation of ReProCS; however, it retains a key limitation of existing work. Principal Components Analysis (PCA) is a widely used dimension reduction technique that finds a small number of orthogonal basis vectors, called principal components, along which most of the variability of the dataset lies. It is well known that PCA is sensitive to outliers. Accurately computing the principal subspace in the presence of outliers is called robust PCA [9, 11, 44, 47]. Often, for time series data, the principal subspace changes gradually over time. Updating its estimate on-the-fly (recursively) in the presence of outliers, as more data comes in, is referred to as online or recursive robust PCA [1, 29, 45]. “Outlier” is a loosely defined term that refers to any corruption that is not small compared to the true data vector and that occurs occasionally. As suggested in [9, 51], an outlier can be nicely modeled as a sparse vector whose nonzero values can have any magnitude.
