CIF: Small: Recursive Robust Principal Components' Analyis (PCA)

Iowa State University, Ames IA

Investigators

Abstract

We develop novel and provably stable polynomial time solutions for solving the recursive robust principal component analysis (PCA) problem. Here, "robust" refers to robustness to both independent and correlated sparse outliers. The goal of PCA is to find the principal component (PC) space, which is the minimum-dimension subspace that spans (or, in practice, approximately spans) a given dataset. Computing the PCs in the presence of outliers is called robust PCA. If the PC space changes over time, there is a need to update the PCs. Doing this recursively is referred to as recursive robust PCA. Key potential applications include automatic foreground extraction from similar-looking backgrounds in video; sensor-network-based detection and tracking of abnormal events such as forest fires; online detection of brain activation patterns from functional MRI sequences; and speech/audio extraction from large but correlated background noise. The key idea is to reformulate this as a problem of recursively recovering a time sequence of sparse signals in the presence of large but correlated noise. The noise must be correlated enough to have an approximately low rank covariance matrix that is either constant or changes slowly. The change in the support of the sparse signal sequences may or may not be slow, but it is highly correlated; e.g. the support can move, expand or deform over time. We ask the following practically relevant questions about performance guarantees of the proposed algorithms. (a) Under what conditions can we prove exact recovery? (b) When can be obtain time-invariant and small error bounds (i.e., show stability)? The research will be included in the curriculum at various levels and in undergraduate senior design and summer research projects.