  This paper presents an algebro-geometric solution to the problem of
segmenting an unknown number of subspaces of unknown and varying dimensions
from sample data points. We represent the subspaces with a set of homogeneous
polynomials whose degree is the number of subspaces and whose derivatives at a
data point give normal vectors to the subspace passing through the point. When
the number of subspaces is known, we show that these polynomials can be
estimated linearly from data; hence, subspace segmentation is reduced to
classifying one point per subspace. We select these points optimally from the
data set by minimizing certain distance function, thus dealing automatically
with moderate noise in the data. A basis for the complement of each subspace is
then recovered by applying standard PCA to the collection of derivatives
(normal vectors). Extensions of GPCA that deal with data in a high- dimensional
space and with an unknown number of subspaces are also presented. Our
experiments on low-dimensional data show that GPCA outperforms existing
algebraic algorithms based on polynomial factorization and provides a good
initialization to iterative techniques such as K-subspaces and Expectation
Maximization. We also present applications of GPCA to computer vision problems
such as face clustering, temporal video segmentation, and 3D motion
segmentation from point correspondences in multiple affine views.
