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

Speaker: Prof. Namrata Vaswani
School of Electrical and Computer Engineering, Iowa State University

Venue: Packard 101
Time: 4:15 pm to 5:15 pm
Date: Thursday, Oct 15, 2015

Abstract

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 version of the above problem, the online problem is largely open. In recent work, we have shown that, with ReProCS, under mild assumptions, 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.

Speaker Bio

Namrata Vaswani received a B.Tech. from 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 postdoc and 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. Her research interests lie at the intersection of signal and information processing, machine learning for high dimensional problems, and applications in computer vision and bioimaging.

Prof. Vaswani has served one term as an Associate Editor for the IEEE Transactions on Signal Processing (2009-2012). She is a recipient of the Harpole-Pentair Assistant Professorship at Iowa State (2008-09), the Iowa State Early Career Engineering Faculty Research Award (2014) and the IEEE Signal Processing Society Best Paper Award (2014).