Open access
Datum
2017-09Typ
- Journal Article
ETH Bibliographie
yes
Altmetrics
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. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000231154Publikationsstatus
publishedExterne Links
Zeitschrift / Serie
Information and Inference: A Journal of the IMABand
Seiten / Artikelnummer
Verlag
Oxford University PressThema
Subspace clustering; Dimensionality reduction; Random projections; Sparse signal recoveryOrganisationseinheit
03610 - Boelcskei, Helmut / Boelcskei, Helmut
Anmerkungen
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.ETH Bibliographie
yes
Altmetrics