Online Subspace Estimation and Tracking from Missing or Corrupt Data

Low-dimensional linear subspace approximations to high-dimensional data are a common approach to handling problems of estimation, detection and prediction, with applications such as network monitoring, collaborative filtering, object tracking in computer vision, and environmental sensing. Corrupt and missing data are the norm in many high-dimensional situations, not only because of errors/failures, but because it may be impossible to collect all the interesting measurements or impractical to compute in real-time using all the data available. Recently developed algorithms for “Matrix Completion” and “Robust PCA” have offered tools to find low-dimensional approximations to data even when data are missing and corrupt. However, these algorithms operate on all the available data at once and assume that the underlying low-dimensional subspace remains constant. This talk describes an alternative called GROUSE (Grassmannian Rank-one Update Subspace Estimation), an incremental algorithm that can handle all the same problems, but does so incrementally, processing one incomplete or corrupted measurement vector at a time. This allows GROUSE to operate with considerably less computation than the other algorithms, while at the same time allowing flexibility for real-time applications such as tracking and anomaly detection. I will present GROUSE and show its application to subspace tracking, matrix completion, robust PCA, and subspace clustering with missing data.