Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear Modeling

Abstract

The problem of Hybrid Linear Modeling (HLM) is to model and segment data using a mixture of affine subspaces. Different strategies have been proposed to solve this problem, however, rigorous analysis justifying their performance is missing. This paper suggests the Theoretical Spectral Curvature Clustering (TSCC) algorithm for solving the HLM problem, and provides careful analysis to justify it. The TSCC algorithm is practically a combination of Govindu's multi-way spectral clustering framework (CVPR 2005) and Ng et al.'s spectral clustering algorithm (NIPS 2001). The main result of this paper states that if the given data is sampled from a mixture of distributions concentrated around affine subspaces, then with high sampling probability the TSCC algorithm segments well the different underlying clusters. The goodness of clustering depends on the within-cluster errors, the between-clusters interaction, and a tuning parameter applied by TSCC. The proof also provides new insights for the analysis of Ng et al. (NIPS 2001).

40 pages. Minor changes to the previous version (mainly revised Sections 2.2 & 2.3, and added references). Accepted to the Journal of Foundations of Computational Mathematics

References in corpus (3)

• Consistency of spectral clustering
• On d-dimensional d-Semimetrics and Simplex-Type Inequalities for High-Dimensional Sine Functions
• High-Dimensional Menger-Type Curvatures-Part II: d-Separation and a Menagerie of Curvatures

Cited by in corpus (11)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Robust subspace clustering
• Hybrid Linear Modeling via Local Best-fit Flats
• Spectral clustering based on local linear approximations
• Robust recovery of multiple subspaces by geometric l_p minimization
• Kernel Spectral Curvature Clustering (KSCC)
• A New Approach To Two-View Motion Segmentation Using Global Dimension Minimization
• High-Dimensional Menger-Type Curvatures-Part II: d-Separation and a Menagerie of Curvatures
• Motion Segmentation by SCC on the Hopkins 155 Database
• Least squares approximations of measures via geometric condition numbers
• Exploring Singularities in point clouds with the graph Laplacian: An explicit approach