Why Subspace Clustering Works on Compressed Data?

Subspace clustering (SC) refers to the problem of clustering unlabeled high-dimensional data into a union of low-dimensional subspaces. In many practical scenarios, one may only have access to the compressed data due to constraints of measurement or computation. In this paper, we introduce a general framework for analyzing the performance of various subspace clustering algorithms when applied to the compressed data. Our framework captures the connection between the problems of compressed subspace clustering (CSC) and noisy subspace clustering. With the existing study of noisy SC, our framework makes it possible to easily extend the results in noisy SC to CSC. In this paper, we apply the framework to a most commonly used sparse subspace clustering (SSC) algorithm and obtain its performance. Finally, the practicability and efficiency of CSC are verified by numerical experiments.