Department Seminar Series: Laura Balzano, Ph.D., Subspace Estimation and Tracking when Data are Missing and Corrupted

Abstract:  Low-dimensional linear subspace approximations to high-dimensional data are powerful enough to capture a great deal of structure in many signals, and yet they also offer simplicity and ease of analysis. Because of this they have provided a powerful tool to many areas of engineering and science: 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 massive datasets, not only because of errors and failures in data collection, but because it may be impossible to collect and process all the desired measurements. In this talk, I will describe recent results on estimating subspace projections from incomplete data and a fundamental theorem that provides a powerful tool for developing algorithms for subspace estimation and tracking with incomplete data. I will focus on the algorithm GROUSE (Grassmannian Rank-One Update Subspace Estimation), a subspace tracking algorithm that performs gradient descent on the Grassmannian (the manifold of all d-dimensional subspaces for a fixed d); I will describe its guarantees and its application to the matrix completion problem. I will also discuss the robust version, GRASTA (Grassmannian Robust Adaptive Sub-space Tracking Algorithm), which is based on the analogous l1 cost function and has been applied successfully to realtime separation of background and foreground in video.