Online Robust Principal Components Analysis

Add to your list(s) Download to your calendar using vCal

• Prof. Namrata Vaswani, Iowa State University
• Thursday 02 July 2015, 14:30-15:30
• LR5, Department of Engineering.

If you have a question about this talk, please contact Prof. Ramji Venkataramanan.

This talk has been canceled/deleted

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 (x_t + l_t) at each time t. The subspace of l_t’s changes slowly enough so that the matrix L_t = [l_1, l_2, ... l_t] is low-rank at each time t. Clearly the matrix X_t = [x_1, x_2, ... x_t] is sparse. Thus this is a problem of online sparse + low-rank matrix recovery from their sum. 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 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.

Bio: 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. Since Fall 2005, she has been with the Iowa State University where she is currently an Associate Professor of Electrical and Computer Engineering. Namrata’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. Namrata has held the Harpole-Pentair Assistant Professorship at Iowa State during 2008-09 and has served one term 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 Best Paper Award for her 2010 TSP paper on Modified-CS.

This talk is part of the Signal Processing and Communications Lab Seminars series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.