Dimensionality-reduced subspace clustering
  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 paper 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.
