Title: 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.