Update

[Oct. 13, 2014]: Papers related to Online Robust PCA by our group are listed in the References of this webpage
[Sept.15, 2014]: Practical ReProCS for Separating Sparse and Low-dimensional Signal Sequences from their Sum -- Part 2 accepted to GlobalSIP 2014
[June 18, 2014]: Practical ReProCS for Separating Sparse and Low-dimensional Signal Sequences from their Sum -- Part 2 summitted to GlobalSIP 2014
[June 10, 2014]: Two new heuristics are implemented (see following discussion)
[May 21, 2014]: Demo code released
[May 20, 2014]: An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum accepted to IEEE Transactions on Signal Processing
[Feb. 3,   2014]: Practical ReProCS for Separating Sparse and Low-dimensional Signall Sequences from their Sum --Part 1 accepted to ICASSP 2014

---

Introduction We designs and evaluate a practical algorithm, called practical recursive projected compressive sensing (Prac-ReProCS), for recoveing a time sequences of sparse vectors St and a time sequences of dense vectors Lt from their sum, Mt: = St+Lt. To be exact, the problem we are trying to solve is fomulated as following: The measurement vector at time t, Mt, can be decomposed as Mt = St + Lt where St is a sparse vector and Lt is a dense but low-dimensional vector Given an intial sequence which does not contain the sparse components, we are able to get an intial subspace Our goal is to recursively estimate St and Lt and the subspace in which the last Lt's lie at each t > t_train The basic algorithm of Prac-ReProCS is summarized in the right column. For a quick understanding, see our poster. For details please see our paper.

---

Video Experiments

Following gifs show the performance (estimating foreground and background) of our algorithm. For foreground, we only show the support in white for ease of display.  Comparison of different algorithms are also shown below in form of streaming media (we compared Prac-ReProCS with PCP, RSL, GRASTA and adapted-iSVD).

original                           foreground                       background               original                           foreground                       background	original                            foreground                       background         original                            foreground                       background
For each triple-gif set,  videos of orignal /foregound/background are converted to gif separately, so their change might not match simultaneously.
If you have problems viewing the embeded Youtube videos above, you can download them here video1 video2 video3 video4. Two new heuristics[June 10, 2014] We added in two new heuristics to help detect the absence of a sparse vector (e.g. when the foreground object moves out of the scene) and to deal with very static backgrounds. The discussion of these can be found here. The gifs below show that, when the sparse vector is absent, adding a fg detection step can make the estimated foreground cleaner.
original                           foreground                       background               original                           foreground                       background	original                            foreground                       background         original                            foreground                       background
For each triple-gif set,  videos of orignal /foregound/background are converted to gif separately, so their change might not match simultaneously. Supplementary Meterial The pure background (for lake and cuntain) we mention in our paper are shown below

---

Code

The demo code can be downloaded here. Please cite our papers if you use it.

---

References (All papers related to OnlineRobust PCA in our group)

Journal Papers 

1. Brian Lois and Namrata Vaswani, A Correctness Result for Online Robust PCA, submitted to IEEE Trans. Information Theory
2. Jinchun Zhan and Namrata Vaswani, Robust PCA with Partial Subspace Knowledge, submitted to IEEE Trans. on Signal Processing
3. Han Guo, Chenlu Qiu and Namrata Vaswani, An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum, IEEE Trans. on Signal Processing,  August 2014
4. Chenlu Qiu, Namrata Vaswani, Brian Lois and Leslie Hogben, Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise, IEEE Trans. Information Theory, August 2014

Conference Papers (reverse chronological order)

1. Han Guo, Chenlu Qiu and Namrata Vaswani, Practical ReProCS for Separating Sparse and Low-dimensional Signal Sequences from their Sum -- Part 2, accepted to IEEE GlobalSIP 2014
2. Jinchun Zhan and Namrata Vaswani, Robust PCA with Partial Subspace Knowledge, IEEE Intl. Symp. Info. Theory (ISIT) 2014
3. Jinchun Zhan and Namrata Vaswani, Performance Guarantees for ReProCS -- Correlated Low-Rank Matrix Entries Case, IEEE Intl. Symp. Info. Theory (ISIT) 2014
4. Han Guo, Chenlu Qiu and Namrata Vaswani, Practical ReProCS for Separating Sparse and Low-dimensional Signall Sequences from their Sum --Part 1, IEEE Intl. Conf. Acous. Speech. Sig. Proc. (ICASSP) 2014
5. Brian Lois, Namrata Vaswani and Chenlu Qiu, Performance Guarantees for Undersampled Recursive Sparse Recovery in Large but Structured Noise, IEEE GlobalSIP, 2013
6. Chenlu Qiu and Namrata Vaswani, Recursive Sparse Recovery in Large but Structured Noise -- Part 2, IEEE Intl. Symp. Info. Theory (ISIT) 2013
7. Chenlu Qiu, Namarata Vaswani and Leslie Hogben, Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise, IEEE Intl. Conf. Acous. Speech. Sig. Proc. (ICASSP), 2013
8. Jinchun Zhan and Namrata Vaswani and Ian Atkinson, Separating Sparse and Low-Dimensional Signal Sequence from Time-varying Undersampled Projections of their Sums, IEEE Intl. Conf. Acous. Speech. Sig. Proc. (ICASSP), 2013
9. Chenlu Qiu and Namrata Vaswani, Recursive Sparse Recovery in Large but Corrected Noise, Allerton 2011
10. Chenlu Qiu and Namrata Vaswani, Real-time Robust Principal Components' Pursuit, Allerton 2010

---