[month] [year]

Nearly Optimal Robust Subspace Tracking (and other Dynamic Structured Big-Data Recovery problems)

Prof. Namrata Vaswani, Professor of Electrical and Computer Engineering, and (by courtesy) of Mathematics, at Iowa State University gave a talk on Nearly Optimal Robust Subspace Tracking (and other Dynamic Structured Big-Data Recovery problems) on 24 July.

A significant fraction of the data generated these days is of a “streaming” nature, i.e., it cannot be stored for too long. Examples include texts, tweets, network traffic, changing Facebook connections, or video surveillance feeds . Moreover, very often, acquired data is an undersampled, outlier-corrupted, or nonlinear (e.g., phaseless) function of the clean data, while the “clean data” usually has structure, e.g., sparsity or low rank. This talk briefly described Prof Vaswani’s work on three such problems – dynamic Compressive Sensing, low-rank Phase Retrieval, and dynamic Robust PCA (Robust Subspace Tracking). The bulk of the talk will focus on the last one.

While PCA is a classical well studied problem, PCA techniques fail if the data is corrupted by anything other than small noise. However, some entries of many modern datasets are often corrupted by outliers (sparse corruptions). Moreover, for long sequences, the subspace in which the data lies also changes with time, albeit gradually. This problem of tracking the low dimensional subspace in which a given dataset lies, in the presence of sparse outliers, is referred to as Robust Subspace Tracking (RST) or dynamic Robust PCA. While the Robust PCA problem has received a lot of attention in the last decade, its dynamic version was largely open until recently. In a recent body of work, Prof Vaswani and her team have introduced the first provably correct, fast, and practically usable solution framework for dynamic robust PCA called Recursive Projected Compressive Sensing (ReProCS).

Her most recent work (ICML 2018) shows that a simple ReProCS-based algorithm called NORST provides an online, fast, and provably nearly (delay and memory) optimal RST solution under mild assumptions: weakened standard RPCA assumptions, slow subspace change, and a lower bound on (most) outlier magnitudes. ReProCS-NORST also has a significantly improved worst-case outlier tolerance compared with all previous robust PCA or RST methods without requiring any model on how the outlier support is generated. For the video application this implies that the foreground moving objects could be slow moving or even occasionally static, and the ReProCS algorithm will still work. We demonstrate this practical advantage via extensive experimental comparisons for two computer vision and video analytics applications: video layering and video denoising.

Prof Vaswani’s research areas are intersection of statistical machine learning and data science, computer vision, and signal processing. Her recent research has been on provable online algorithms for various dynamic structured high-dimensional (big) data recovery problems such as dynamic compressive sensing (CS), dynamic robust principal component analysis (RPCA), and phase retrieval (ongoing work).

She is an Area Editor for IEEE Signal Processing Magazine, has served twice as an Associate Editor for IEEE Transactions on Signal Processing, and is the Lead Guest Editor for a Proceedings IEEE Special Issue on Rethinking PCA for Modern Datasets that will appear in August 2018. She is also the Chair of the Women in Signal Processing (WiSP) Committee and a steering committee member of SPS’s Data Science Initiative.