We consider the problem of clustering data lying on multiple subspaces of unknown and possibly different dimensions. We show that one can represent the subspaces with a set of polynomials whose derivatives at a data point give normal vectors to the subspace associated with the data point. Since the polynomials can be estimated linearly from data subspace clustering is reduced to classifying one point per subspace. We do so by choosing points in the data set that minimize a distance function. A basis for the complement of each subspace is then recovered by applying standard PCA to the set of derivatives (normal vectors) at those points. The final result is a new GPCA algorithm for subspace clustering based on simple linear and polynomial algebra. Our experiments show that our method outperforms existing algebraic algorithms based on polynomial factorization and provides a good initialization to iterative techniques such as K-subspace and EM. We also present applications of GPCA on computer vision problems such as vanishing point detection, face clustering, and news video segmentation.
A new GPCA algorithm for clustering subspaces by fitting, differentiating and dividing polynomials
2004-01-01
479495 byte
Conference paper
Electronic Resource
English
A New GPCA Algorithm for Clustering Subspaces by Fitting, Differentiating and Dividing Polynomials
British Library Conference Proceedings | 2004
|Minimum Effective Dimension for Mixtures of Subspaces: A Robust GPCA Algorithm and Its Applications
British Library Conference Proceedings | 2004
|Online Contents | 2014
Generalized Principal Component Analysis (GPCA)
British Library Conference Proceedings | 2003
|