Sketched Subspace Clustering

Abstract

The immense amount of daily generated and communicated data presents unique challenges in their processing. Clustering, the grouping of data without the presence of ground-truth labels, is an important tool for drawing inferences from data. Subspace clustering (SC) is a relatively recent method that is able to successfully classify nonlinearly separable data in a multitude of settings. In spite of their high clustering accuracy, SC methods incur prohibitively high computational complexity when processing large volumes of high-dimensional data. Inspired by random sketching approaches for dimensionality reduction, the present paper introduces a randomized scheme for SC, termed Sketch-SC, tailored for large volumes of high-dimensional data. Sketch-SC accelerates the computationally heavy parts of state-of-the-art SC approaches by compressing the data matrix across both dimensions using random projections, thus enabling fast and accurate large-scale SC. Performance analysis as well as extensive numerical tests on real data corroborate the potential of Sketch-SC and its competitive performance relative to state-of-the-art scalable SC approaches.

arXiv commentP. A. Traganitis and G. B. Giannakis, "Sketched Subspace Clustering," IEEE Transactions on Signal Processing, vol. 66, to appear 2018

References in corpus (11)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• Sketching as a Tool for Numerical Linear Algebra
• Median K-flats for hybrid linear modeling with many outliers
• A Unified Framework for Representation-based Subspace Clustering of Out-of-sample and Large-scale Data
• Hybrid Linear Modeling via Local Best-fit Flats
• Innovation Pursuit: A New Approach to Subspace Clustering
• Preconditioned Data Sparsification for Big Data with Applications to PCA and K-means
• Sketch and Validate for Big Data Clustering
• Randomized Dimensionality Reduction for k-means Clustering
• Randomized sketches for kernels: Fast and optimal non-parametric regression
• A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data

Cited by in corpus (8)

• Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
• Efficient Solvers for Sparse Subspace Clustering
• Sketched Multi-view Subspace Learning for Hyperspectral Anomalous Change Detection
• Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
• Online Sparse Subspace Clustering
• Stochastic Sparse Subspace Clustering
• Label-independent hyperparameter-free self-supervised single-view deep subspace clustering
• Learning a Self-Expressive Network for Subspace Clustering