Dimensionality-reduced subspace clustering

Reinhard Heckel, Michael Tschannen, Helmut Bölcskei

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

Subspace clustering refers to the problem of clustering unlabeled high-dimensional data points into a union of low-dimensional linear subspaces, whose number, orientations and dimensions are all unknown. In practice, one may have access to dimensionality-reduced observations of the data only, resulting, e.g., from undersampling due to complexity and speed constraints on the acquisition device or mechanism. More pertinently, even if the high-dimensional data set is available, it is often desirable to first project the data points into a lower-dimensional space and to perform clustering there; this reduces storage requirements and computational cost. The purpose of this article is to quantify the impact of dimensionality reduction through random projection on the performance of three subspace clustering algorithms, all of which are based on principles from sparse signal recovery. Specifically, we analyze the thresholding based subspace clustering (TSC) algorithm, the sparse subspace clustering (SSC) algorithm and an orthogonal matching pursuit variant thereof (SSC-OMP).We find, for all three algorithms, that dimensionality reduction down to the order of the subspace dimensions is possible without incurring significant performance degradation. Moreover, these results are order-wise optimal in the sense that reducing the dimensionality further leads to a fundamentally ill-posed clustering problem. Our findings carry over to the noisy case as illustrated through analytical results for TSC and simulations for SSC and SSC-OMP. Extensive experiments on synthetic and real data complement our theoretical findings.

Original languageEnglish
Pages (from-to)246-283
Number of pages38
JournalInformation and Inference
Volume6
Issue number3
DOIs
StatePublished - 1 Sep 2017
Externally publishedYes

Keywords

  • Dimensionality reduction
  • Random projection
  • Sparse signal recovery
  • Subspace clustering

Fingerprint

Dive into the research topics of 'Dimensionality-reduced subspace clustering'. Together they form a unique fingerprint.

Cite this