We introduce a novel and provably correct solution approach, called ReProCS, to the online dynamic robust principal components' analysis (PCA) problem. Robust PCA (RPCA) can be understood as a problem of separating a low-rank matrix of the true data, L, and a sparse matrix of outliers, S, from their sum, Y = L + S. Application domains include computer vision and data analytics, among others. For example, the problem of separating sparse foregrounds (e.g., moving objects) from slowly changing backgrounds in video sequences can be posed as an instance of RPCA. This is a key first step in simplifying many computer vision tasks, e.g., video surveillance, low-bandwidth mobile video chats and video conferencing, low-light imaging ("seeing moving objects in the dark") and video denoising. RPCA solutions are also very useful in solving product recommender systems' design problems, such as the Netflix problem, when the user data may contain outliers (e.g., due to lazy or malicious users). While there has been a large amount of recent work on provably correct batch RPCA solutions, the online and dynamic RPCA problem is largely open. Online dynamic RPCA is the problem of solving RPCA on-the-fly, with the extra assumptions that the initial subspace is accurately known and that the subspace from which the true data is generated is either fixed or changes slowly over time. For most of the applications discussed above, an online solution is clearly preferable and it can argued that these extra assumptions hold. We demonstrate the power of our proposed ReProCS based online dynamic RPCA solution for many of the above applications. Moreover, under mild assumptions, we show that, with high probability, ReProCS recovers the support of the outliers exactly at all times; the subspace in which the true data lies is tracked accurately; and the error in the estimates of both is small at all times.
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 data science and statistical machine learning, signal and information processing, 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).