Generalized Principal Component Analysis (GPCA) and its application to segmentation of dynamics scenes

Rene Vidal, Electrical Engineering and Computer Science, University of California, Berkeley

Model-based data segmentation is usually though of as a "chiken and egg" problem in which, in order to estimate the model for each class one needs to first segment the data and in order to segment the data one needs to know the model defining each class.

In this talk we will show that this "chicken and egg" dilema can be completely solved when the model defining each of the n classes is a linear k-dimensional subspace of a K-dimensional linear space. We cast the GPCA problem in an algebraic geometric framework in which the number of classes becomes the degree of a certain polynomial and the classes themselves become the factors (roots) of such a polynomial. With this interpretation in mind, we show that the GPCA problem is equivalent to a factorization problem in the space of homogeneous polynomials of degree n in K variables. We prove that such a problem has a unique solution which can be obtained in polynomial time using linear algebraic techniques. Furthermore, we show that GPCA has a closed form solution when n <= 4. The number of subspaces n can be obtained from the rank of a certain matrix that depends on the data.

We present applications of GPCA on segmentation of dynamic scenes (3D and affine) and eigenvector segmentation.