Online Robust PCA or Online Sparse Matrix Recovery from Large but Structured Noise

Friday, November 07, 2014
UTA 7.532

This work studies the problem of sequentially recovering a sparse vector x_t and a vector from a low-dimensional subspace l_t from knowledge of their sum m_t=x_t+l_t. If the primary goal is to recover the low-dimensional subspace where the l_t'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. We develop a novel algorithm called ReProCS to solve this problem and demonstrate its significant advantage over other robust PCA based methods for the video analysis problem. 

We prove that if the l_t's obey certain denseness and slow subspace change assumptions, the support of x_t changes by at least a certain amount at least every so often, and some other mild assumptions hold, then with high probability, the support of x_t will be recovered exactly. Also, the error made in estimating x_t and l_t will be small and the subspace recovery error will be decay to a small value within a short delay of a subspace change time. To the best of our knowledge, this is the first complete correctness result for online robust PCA or equivalently for online sparse plus low-rank recovery.


Associate Professor
Iowa State University

Namrata Vaswani received a B.Tech. from Indian Institute of Technology (IIT), Delhi, in 1999 and a Ph.D. from University of Maryland, College Park, in 2004, both in Electrical Engineering. During 2004-05, she was a research scientist at Georgia Tech. Since Fall 2005, she has been with the Iowa State University where she is currently an associate professor of electrical and computer engineering. She held the Harpole-Pentair assistant professorship during 2008-09 and received the Early Career Engineering Faculty Research Award in 2014. During 2009 to 2013, she has served as an Associate Editor for IEEE Transactions on Signal Processing.

Vaswani's research interests are in machine learning for high dimensional problems, signal and information processing and in imaging. Her current work focuses on recursive sparse recovery, online robust PCA, matrix completion and applications in video analytics and medical imaging.