We study the problem of recursively recovering a sequence of sparse vectors from highly corrupted observations. At each time, we have

                       observed measurement = sparse signal + dense noise                                                (1)

The dense noise can has much larger energy than the sparse signals. However, the noise sequence is highly correlated over time and therefore lying in a slowly changing low dimensional subspace.

Suppose an initial estimate of the noise subspace is available (i.e., estimate initial noise subspace from training sequence). The original noise can be approximately nullify by computing an orthogonal projection of the observed  measurement onto the noise null subspace and get

                       projected measurement = projection matrix * sparse signal + projected noise                (2)

The original problem (1) is transformed into a standard compressive sensing / sparse recovery problem (2) with the projected noise being much smaller. The sparse signal can be recovered from the projected measurements via any standard L1 minimization approaches. With an estimate of the sparse signal, we get an estimate of the noise and hence update the noise subspace every-so-often.

Applications:

A key application is in video surveillance where the goal is to separate a slowly changing background from moving foreground objects on-the-fly. The background sequence is well modeled as lying in a low dimensional subspace, that can gradually change over time, while the moving foreground objects constitute the correlated sparse signals.

Other possible applications include online fMRI based organ active region detection problem or sensor networks based detection and tracking of abnormal events such as forest fires or oil spills, etc.

Some experiment results can be found here and here (old).

Papers:

• Chenlu Qiu and Namrata Vaswani, Automated Recursive Projected CS (ReProCS) for Real-time Video Layering, submitted to CVPR 2012.
• Chenlu Qiu and Namrata Vaswani, ReProCS: A Missing Link between Recursive Robust PCA and Recursive Sparse Recovery in Large but Correlated Noise,  arXiV: 1106.3286.
• Chenlu Qiu and Namrata Vaswani, Recursive Sparse Recovery in Large but Low Dimensional Noise, 48th Allerton Conference on Communication Control  and Computing, 2011.
• Chenlu Qiu and Namrata Vaswani, Support Predicted Modified-CS for Recursive Robust Principal Components' Pursuit, ISIT 2011.
• Chenlu Qiu and Namrata Vaswani, Real-time Robust Principal Components' Pursuit, Allerton, 2010.

Matlab code: ReProCS_code.zip  ( Please cite above papers if you use this code. )