Scalable Robust Principal Component Analysis Using Grassmann Averages

• Published in: IEEE transactions on pattern analysis and machine intelligence 2016-11, Vol.38 (11), p.2298-2311
• Main Authors: Hauberg, Sren, Feragen, Aasa, Enficiaud, Raffi, Black, Michael J.
• Format: Article
• Language: English
• Subjects: Approximation methods; Complexity theory; Computer vision; Dimensionality reduction; Estimation; Manifolds; Principal component analysis; Principal components analysis; robust principal component analysis; Robustness; subspace estimation
• ISSN: 0162-8828; 1939-3539; 2160-9292
• DOI: 10.1109/TPAMI.2015.2511743

In large datasets, manual data verification is impossible, and we must expect the number of outliers to increase with data size. While principal component analysis (PCA) can reduce data size, and scalable solutions exist, it is well-known that outliers can arbitrarily corrupt the results. Unfortunately, state-of-the-art approaches for robust PCA are not scalable. We note that in a zero-mean dataset, each observation spans a one-dimensional subspace, giving a point on the Grassmann manifold. We show that the average subspace corresponds to the leading principal component for Gaussian data. We provide a simple algorithm for computing this Grassmann Average (GA), and show that the subspace estimate is less sensitive to outliers than PCA for general distributions. Because averages can be efficiently computed, we immediately gain scalability. We exploit robust averaging to formulate the Robust Grassmann Average (RGA) as a form of robust PCA. The resulting Trimmed Grassmann Average (TGA) is appropriate for computer vision because it is robust to pixel outliers. The algorithm has linear computational complexity and minimal memory requirements. We demonstrate TGA for background modeling, video restoration, and shadow removal. We show scalability by performing robust PCA on the entire Star Wars IV movie; a task beyond any current method. Source code is available online.