The Software Workshop is a unique central scientific facility that brings together scientists and software engineers to translate basic research into software systems that can be used internally and deployed.
The Grassmann Averages PCA is a method for extracting the principal components from a sets of vectors, with the nice following properties: 1) it is of linear complexity wrt. the dimension of the vectors and the size of the data, which makes the method highly scalable, 2) It is more robust to outliers than PCA in the sense that it minimizes an L1 norm instead of the L2 norm of the standard PCA.
It comes with two variants: 1) the standard computation, that coincides with the PCA for normally distributed data, also referred to as the GA, 2) a trimmed variant, that is more robust to outliers, referred to the TGA.
We provide implementations for the Grassmann Average, the Trimmed Grassmann Average, and the Grassmann Median. The simplest is the Matlab implementation used in the CVPR 2014 paper, but we also provide a faster C++ implementation, which can be used either directly from C++ or through a Matlab wrapper interface.
The repository contains the following:
a C++ multi-threaded implementation of the GA and TGA
a C++ multi-threaded implementation of the EM-PCA (for comparisons)
binaries that computes the GA, TGA and EM-PCA on a set of images (frames of a video)
IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), December 2015 (article)
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.
The Max Planck Institute for Intelligent Systems in Tübingen, Germany, is a leading center for research in computer vision, robotics, and machine learning. Our research seeks to understand mathematical principles of intelligent systems. Part of the institute, the Software Workshop is a unique Central Scientific Facility at the intersection of research and software engineering. We bring together scientists and software engineers to help improve the research of the institute by translating it into high quality software products and promoting it worldwide.
Unser Ziel ist es, die Prinzipien von Wahrnehmen, Lernen und Handeln in autonomen Systemen zu verstehen, die mit komplexen Umgebungen interagieren. Das Verständnis wollen wir nutzen, um künstliche intelligente Systeme zu entwickeln.