Generalized principal component analysis (GPCA)

By René Vidal, Yi Ma, S. Sastry. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005

1,199 citations recorded by the source corpus.

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.

Subfields: Analytical Chemistry, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/ff813686f1ec42b3713ec37a327dcc50eec0962f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Analytical Chemistry

In Computer Vision and Pattern Recognition

Citations in the corpus

A General Framework for Motion Segmentation: Independent, Articulated, Rigid, Non-rigid, Degenerate and Non-degenerate (2006, background): “[18][19][20] propose an algebraic framework called GPCA that can deal with dependent and independent subspaces with unknown dimensionality uniformly.”
Learning Sets with Separating Kernels (2012, methodology): “This observation has motivated considering more general situations such as manifold plus noise models [17, 47], and models where the data are described by combinations of more than one manifold [41, 70].”
Big data for cyber physical systems in industry 4.0: a survey (2019, methodology): “The typical methods in this type include GPCA (Vidal, Ma, and Sastry 2005), SSC (Elhamifar and Vidal 2013), and RSC (Soltanolkotabi, Elhamifar, and Candes 2014).”
Sparse subspace clustering (2009, methodology): “However, GPCA is sensitive to noise and outliers , and its complexity increases exponentially with the number of subspaces and their dimensions.”
Robust Subspace Clustering (2013, background): “In this area, a mathematically intriguing approach is the generalized principal component analysis (GPCA) presented in [54].”
Multiframe Motion Segmentation with Missing Data Using PowerFactorization and GPCA (2008, positive): “More generally the principle is (Vidal et al. 2005) The same principle applies to the motion segmentation problem.”
Robust Multiple Structures Estimation with J-Linkage (2008, methodology): “Also the algebraic technique presented in [6] is effective in estimating multiple models, but it is not robust to gross outliers.”
Dictionaries for Sparse Representation Modeling (2010, background): “Sastry [ 82 ], offers a different and very interesting approach to overcomplete dictionary design.”
Visual SLAM and Structure from Motion in Dynamic Environments (2018, methodology): “[164, 165] proposed Generalized Principal Component Analysis (GPCA) as an extension of PCA.”
A Benchmark for the Comparison of 3-D Motion Segmentation Algorithms (2007, methodology): “Generalized PCA (GPCA) [17, 16] Generalized Principal Component Analysis (GPCA) is an algebraic method for clustering data lying in multiple subspaces proposed by Vidal et al .”
Semi-supervised Learning with GANs: Manifold Invariance with Improved Inference (2017, background): “The problem of learning a smooth manifold from finite samples has been studied in the literature[5, 2, 27, 6, 40, 19, 14, 3], and it is an interesting problem in its own right to study the manifold approximation error of GANs, which minimize a chosen divergence measure between the data distribution ”
Generalized BackPropagation, Étude De Cas: Orthogonality (2016, background): “…but not limited to dimensionality reduction Turk and Pentland (1991); Hyvarinen (1999); Cai et al. (2006); Cunningham and Ghahra-mani (2015), clustering Niu et al. (2010); Kumar et al. (2011), feature selection Yu and Liu (2004) and dictionary learning Lesage et al. (2005); Vidal et al. (2005).”
Solving Inverse Problems With Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity (2010, methodology): “The generalized PCA [75] models and segments data using an algebraic subspace clustering technique based on polynomial fitting and differentiation, and while it has been shown effective in image segmentation, it does not reach the state of the art in image restoration.”
Unifying Image Plane Liftings for Central Catadioptric and Dioptric Cameras (2006, background): “This polynomial embedding preserves homogeneity and is suitable to represent quadratic relations between image points [4, 13].”
Generalized Autoencoder: A Neural Network Framework for Dimensionality Reduction (2014, background): “Principal Component Analysis (PCA) is one of the most popular linear dimensionality reduction techniques [10][17].”
Motion Segmentation in the Presence of Outlying, Incomplete, or Corrupted Trajectories (2010, methodology): “In principle, algebraic methods such as GPCA can be extended to deal with missing data [27] and outliers [32].”
A closed form solution to robust subspace estimation and clustering (2011, methodology): “Therefore, more recent techniques, such as Generalized Principal Component Analysis (GPCA) [20], seek to simultaneously cluster the data into multiple subspaces and find a low-dimensional subspace fitting each group of points.”