Robust and Phaseless PCA (and Subspace Tracking)

Namrata Vaswani
Iowa State University
Monday, March 11, 2019 - 1:25pm to 2:25pm
Lind 305

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 sa