Foundations of a multi-way spectral clustering framework for Hybrid Linear Modeling

Guangliang Chen, Gilad Lerman

Research output: Contribution to journalArticlepeer-review

54 Scopus citations

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).

Original languageEnglish (US)
Pages (from-to)517-558
Number of pages42
JournalFoundations of Computational Mathematics
Volume9
Issue number5
DOIs
StatePublished - Oct 2009

Bibliographical note

Funding Information:
This work was supported by NSF grant #0612608.

Keywords

  • Concentration inequalities
  • D-flats clustering
  • Hybrid linear modeling
  • Multi-way clustering
  • Perturbation analysis
  • Polar curvature
  • Spectral clustering

Fingerprint

Dive into the research topics of 'Foundations of a multi-way spectral clustering framework for Hybrid Linear Modeling'. Together they form a unique fingerprint.

Cite this