Robust and Phaseless PCA (and Subspace Tracking)

Monday, March 11, 2019 - 1:25pm - 2:25pm
Lind 305
Namrata Vaswani (Iowa State University)
Principal Components Analysis (PCA), a.k.a. subspace learning, is one of the most widely used dimension reduction techniques that attempts to find a low-dimensional subspace approximation of a given dataset. PCA is a solved problem when the observed data is relatively clean and lies in (or close to) a low-dimensional subspace. However, in many modern applications, the data are often either incomplete (missing data) or corrupted by outliers. Robust PCA refers to this harder problem of PCA in the presence of entry-wise outliers (sparse corruptions). An important example application is video analytics when slow-changing videos are corrupted by foreground occlusions, e.g., by moving vehicles or persons. For long data sequences, e.g., long surveillance videos, if one tries to use a single subspace to represent the entire sequence, the required subspace dimension may be too large. For such data, a better model is to assume that the data subspace can change with time, albeit gradually. This problem of tracking data lying in a slowly changing subspace, while being robust to additive sparse outliers is referred to as Robust Subspace Tracking (RST). While robust PCA has received a lot of attention in the last decade, its dynamic version, RST, was largely open until recently. In a recent body of work, we have introduced the first provably correct and practically usable online solution framework for RST that we call Recursive Projected Compressive Sensing (ReProCS). Our most recent work from ICML 2018 shows that a simple ReProCS-based algorithm provides a provably fast and nearly (delay and memory) optimal RST solution under mild assumptions: weakened standard robust PCA assumptions and subspace change that is slow enough compared to the smallest magnitude outlier entry. Our theoretical claims are also backed by extensive experimental evidence for two video applications.

In new work, we have looked at what can be called the Phaseless PCA’’ problem. This involves recovering a low-rank matrix from phaseless (magnitude-only) linear projections of each of its columns. It finds important applications in dynamic phaseless imaging applications, such as dynamic sub-diffraction imaging or Fourier ptychography, involving recovering a set of slowly-changing images that together form an approximately low-rank matrix (with each vectorized image being one column). We introduce a simple alternating minimization solution that can provable recover the low-rank matrix with sample complexity that is close to optimal in the low-enough rank regime. The only assumption we need on the matrix is incoherence of right singular vectors.

Namrata Vaswani is a Professor of Electrical and Computer Engineering at Iowa State University. She received a Ph.D. in 2004 from the University of Maryland, College Park and a B.Tech. in 1999 from IIT-Delhi. Her research interests are in data science and include statistical machine learning, signal processing, and computer vision. She received the 2014 Iowa State Early Career Engineering Faculty Research Award as well as the 2014 IEEE Signal Processing Society Best Paper Award (for her Modified-CS work co-authored with her graduate student Lu in IEEE Transactions on Signal Processing). Vaswani is a Fellow of the IEEE (class of 2019).