Scalable robust principal component analysis using Grassmann averages

Publikation: Bidrag til tidsskriftTidsskriftartikelfagfællebedømt

  • Søren Hauberg
  • Aasa Feragen
  • Raffi Enficiaud
  • Michael J. Black
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.
OriginalsprogEngelsk
TidsskriftIEEE Transactions on Pattern Analysis and Machine Intelligence
Vol/bind38
Udgave nummer11
Sider (fra-til)2298-2311
Antal sider14
ISSN0162-8828
DOI
StatusUdgivet - 2016

    Forskningsområder

  • Gaussian processes, data handling, image processing, principal component analysis, GA, Gaussian data, Grassmann Average, Grassmann manifold, RGA, Robust Grassmann Average, TGA, Trimmed Grassmann average, average subspace, computer vision, data size, data verification, grassmann averages, one dimensional subspace, pixel outliers, robust PCA, scalable robust principal component analysis, simple algorithm, zero mean dataset, Approximation methods, Complexity theory, Computer vision, Estimation, Manifolds, Principal component analysis, Robustness, Dimensionality reduction, robust principal component analysis, subspace estimation

ID: 168251565