Generalized Principal Component Analysis (GPCA)

Rene Vidal and Yi Ma1
(Professor S. Shankar Sastry)
(ONR) N00014-00-1-0621

We consider the problem of identifying n linear subspaces in a K-dimensional linear space from a collection of sample points drawn from these subspaces.

In the absence of noise, we cast GPCA in an algebraic geometric framework in which the number of classes n becomes the degree of a certain polynomial and the classes themselves become the factors (roots) of such a polynomial. For subspaces of dimension k=K-1, we show that GPCA is equivalent to factoring homogeneous polynomials of degree n in K variables, and provide a polynomial time solution to this problem using linear algebraic techniques. For subspaces of arbitrary dimension k < K-1, we show that GPCA can be reduced to the case k = K'-1 by first projecting the data into a K'-dimensional subspace of RK.

In the presence of noise, we cast GPCA as a constrained nonlinear least squares problem which minimizes the reprojection error subject to all mixture constraints. By converting this constrained problem into an unconstrained one, we obtain an optimal function from which the subspaces can be directly recovered using standard non-linear optimization techniques. We use the algebraic solution to initialize maximum likelihood algorithms based on nonlinear optimization or iterative algorithms such as EM.

GPCA can be applied to a variety of estimation problems in which the data comes simultaneously from multiple (approximately) linear models. We apply GPCA to the multibody 3D and affine structure from motion problem in computer vision, i.e., the problem of estimating the 3D motion of multiple moving objects from 2D imagery. We also apply GPCA to image segmentation and eigenvector segmentation.


Figure 1: Generalized principal component analysis: the case of 2 lines in the XY plane

[1]
R. Vidal, Y. Ma, and S. Sastry, Generalized Principal Component Analysis, UC Berkeley Electronics Research Laboratory, Memorandum No. UCB/ERL M02/15, May 2002.
1Professor, University of Illinois at Urbana Champaign

More information (http://www.eecs.berkeley.edu/~rvidal/) or

Send mail to the author : (rvidal@eecs.berkeley.edu)


Edit this abstract