Spectral clustering based on local linear approximations

Abstract

In the context of clustering, we assume a generative model where each cluster is the result of sampling points in the neighborhood of an embedded smooth surface; the sample may be contaminated with outliers, which are modeled as points sampled in space away from the clusters. We consider a prototype for a higher-order spectral clustering method based on the residual from a local linear approximation. We obtain theoretical guarantees for this algorithm and show that, in terms of both separation and robustness to outliers, it outperforms the standard spectral clustering algorithm (based on pairwise distances) of Ng, Jordan and Weiss (NIPS '01). The optimal choice for some of the tuning parameters depends on the dimension and thickness of the clusters. We provide estimators that come close enough for our theoretical purposes. We also discuss the cases of clusters of mixed dimensions and of clusters that are generated from smoother surfaces. In our experiments, this algorithm is shown to outperform pairwise spectral clustering on both simulated and real data.

References in corpus (5)

• Consistency of spectral clustering
• Optimal construction of k-nearest neighbor graphs for identifying noisy clusters
• Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear Modeling
• Kernel Spectral Curvature Clustering (KSCC)
• Operator norm convergence of spectral clustering on level sets

Cited by in corpus (20)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Robust subspace clustering
• Hybrid Linear Modeling via Local Best-fit Flats
• An Overview of Robust Subspace Recovery
• A Novel M-Estimator for Robust PCA
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Spectral Clustering Based on Local PCA
• Robust recovery of multiple subspaces by geometric l_p minimization
• Learning by Unsupervised Nonlinear Diffusion
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• A New Approach To Two-View Motion Segmentation Using Global Dimension Minimization
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• lp-Recovery of the Most Significant Subspace among Multiple Subspaces with Outliers
• Probabilistic Recovery of Multiple Subspaces in Point Clouds by Geometric lp Minimization
• Provable Self-Representation Based Outlier Detection in a Union of Subspaces
• Statistical Analysis of Metric Graph Reconstruction
• Least squares approximations of measures via geometric condition numbers
• The Shape of Data and Probability Measures
• Cubical Covers of Sets in ${\mathbb{R}}^n$
• Distributional limits of graph cuts on discretized grids