Spectral clustering based on local linear approximations
From MaRDI portal
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.
Recommendations
Cites work
- A survey of kernel and spectral methods for clustering
- A unified algebraic approach to 2-D and 3-D motion segmentation and estimation
- Asymptotical minimax recovery of sets with smooth boundaries
- Cluster Identification in Nearest-Neighbor Graphs
- Clustering Based on Pairwise Distances When the Data is of Mixed Dimensions
- Connect the dots: how many random points can a regular curve pass through?
- Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection
- Consistency of spectral clustering
- Curvature Measures
- Detection of Abnormal Behavior Via Nonparametric Estimation of the Support
- Detection of non-random patterns in cosmological gravitational clustering
- Estimation of Subspace Arrangements with Applications in Modeling and Segmenting Mixed Data
- Fast multiscale clustering and manifold identification
- Finding the homology of submanifolds with high confidence from random samples
- Foundations of a multi-way spectral clustering framework for hybrid linear modeling
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Image manifolds which are isometric to Euclidean space
- Lanczos Algorithms for Large Symmetric Eigenvalue Computations
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Measuring the strangeness of strange attractors
- Metric entropy of some classes of sets with differentiable boundaries
- Networks of polynomial pieces with application to the analysis of point clouds and images
- On the Volume of Tubes
- Operator norm convergence of spectral clustering on level sets
- Optimal construction of \(k\)-nearest-neighbor graphs for identifying noisy clusters
- Random Geometric Graphs
- Robust algebraic segmentation of mixed rigid-body and planar motions from two views
- The Generic Chaining
Cited in
(28)- A distributed framework for trimmed kernel \(k\)-means clustering
- Spectral nonlinearly embedded clustering algorithm
- Hybrid linear modeling via local best-fit flats
- Random walk distances in data clustering and applications
- Laplacian and signless Laplacian spectra and energies of multi-step wheels
- A multiscale environment for learning by diffusion
- Statistical analysis of a hierarchical clustering algorithm with outliers
- Spectral analysis of 2D outlier layout
- Robust subspace clustering
- The shape of data and probability measures
- Learning the geometric structure of manifolds with singularities using the tensor voting graph
- A dynamic programming approach for distributing quantum circuits by bipartite graphs
- scientific article; zbMATH DE number 6381736 (Why is no real title available?)
- Least squares approximations of measures via geometric condition numbers
- The Fiedler vector of a Laplacian tensor for hypergraph partitioning
- A well-tempered landscape for non-convex robust subspace recovery
- Remember the curse of dimensionality: the case of goodness-of-fit testing in arbitrary dimension
- l_p-recovery of the most significant subspace among multiple subspaces with outliers
- scientific article; zbMATH DE number 7255037 (Why is no real title available?)
- Learning by unsupervised nonlinear diffusion
- Spectral clustering based on local PCA
- A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers
- Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
- Distributional limits of graph cuts on discretized grids
- The Gauss-cos model for the autocorrelation function of fertility rate
- Geometric clustering of point clouds using the spheres method in parametric design
- Foundations of a multi-way spectral clustering framework for hybrid linear modeling
- A new approach to two-view motion segmentation using global dimension minimization
This page was built for publication: Spectral clustering based on local linear approximations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1952238)
