Robust Subspace Clustering via Thresholding

DOI10.1109/TIT.2015.2472520MaRDI QIDQ2977140zbMATH OpenOpenAlexFDO

Authors Reinhard Heckel, Helmut Bölcskei

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4891

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Image analysis in multivariate analysis (62H35) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: The problem of clustering noisy and incompletely observed high-dimensional data points into a union of low-dimensional subspaces and a set of outliers is considered. The number of subspaces, their dimensions, and their orientations are assumed unknown. We propose a simple low-complexity subspace clustering algorithm, which applies spectral clustering to an adjacency matrix obtained by thresholding the correlations between data points. In other words, the adjacency matrix is constructed from the nearest neighbors of each data point in spherical distance. A statistical performance analysis shows that the algorithm exhibits robustness to additive noise and succeeds even when the subspaces intersect. Specifically, our results reveal an explicit tradeoff between the affinity of the subspaces and the tolerable noise level. We furthermore prove that the algorithm succeeds even when the data points are incompletely observed with the number of missing entries allowed to be (up to a log-factor) linear in the ambient dimension. We also propose a simple scheme that provably detects outliers, and we present numerical results on real and synthetic data.

Recommendations

• Robust subspace clustering
• A robust subspace clustering algorithm
• Robust Subspace Clustering With Complex Noise
• Robust subspace clustering based on non-convex low-rank approximation and adaptive kernel
• Subspace clustering through sub-clusters
• A framework for robust subspace learning

Cited in

(12)

• Nonconvex tensorial submodule clustering of 2-D images by mining local and global structural information
• Local nearest neighbour classification with applications to semi-supervised learning
• Threshold-based declustering
• Robust subspace clustering based on automatic weighted multiple kernel learning
• Dimensionality-reduced subspace clustering
• Rigorous restricted isometry property of low-dimensional subspaces
• scientific article; zbMATH DE number 7370570 (Why is no real title available?)
• Beyond linear subspace clustering: a comparative study of nonlinear manifold clustering algorithms
• Kernel truncated regression representation for robust subspace clustering
• A nearest-neighbor based nonparametric test for viral remodeling in heterogeneous single-cell proteomic data
• Robust subspace clustering based on non-convex low-rank approximation and adaptive kernel
• Statistical insights into deep neural network learning in subspace classification

This page was built for publication: Robust Subspace Clustering via Thresholding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977140)