Online Robust PCA or Online Sparse + Low-Rank Matrix Recovery

This work studies the problem of sequentially recovering a time sequence of sparse vectors x_t and vectors from a low-dimensional subspace l_t from knowledge of their sum m_t:=x_t+l_t at each time t. If the primary goal is to recover the low-dimensional subspace in which the l_t's lie, then the problem is one of online 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 our work, we have developed a novel algorithm called ReProCS to solve this problem and demonstrated its significant advantage over other robust PCA based methods for the video layering problem. While there has been a large amount of recent work on performance guarantees for the batch robust PCA or the batch sparse + low-rank matrix recovery problem, the online problem is largely open. In recent work, we have shown that, with ReProCS, under mild assumptions and with high probability, the error in recovering the subspace in which l_t lies decays to a small value within a short delay of a subspace change time and the support of x_t is recovered exactly. Moreover, the error made in estimating x_t and l_t is small at all times. The assumptions that we need are (a) a good estimate of the initial subspace is available (easy to obtain using a short sequence of background-only frames in video surveillance); (b) the l_t's obey a `slow subspace change' assumption; (c) the basis vectors for the subspace from which l_t is generated are dense (non-sparse); and (d) the support of x_t changes by at least a certain amount at least every so often. (based on joint work with Cheniu Qiu and Brian Lois)
Namrata Vaswani received a B.Tech. from the Indian Institute of Technology (IIT), Delhi, in 1999 and a Ph.D. from the 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 has held the Harpole-Pentair Assistant Professorship at Iowa State during 2008-09. From October 2009 to February 2013, she served as an Associate Editor for the IEEE Transactions on Signal Processing (TSP). She is the recipient of the 2014 Iowa State Early Career Engineering Faculty Research Award and the 2014 IEEE Signal Processing Society (SPS) Best Paper Award for her 2010 paper in TSP (jointly with her former graduate student Wei Lu). Vaswani's research interests lie at the intersection of signal and information processing and machine learning for high dimensional problems. She also works on applications in big-data, video analytics and bio-imaging. In the last several years her work has focused on developing provably accurate online algorithms for high-dimensional structured data recovery problems such as online sparse matrix recovery (recursive recovery of sparse vector sequences) or dynamic compressed sensing, online robust principal components' analysis (PCA) and online matrix completion; and on demonstrating their usefulness in dynamic magnetic resonance imaging (MRI) and video analytics.