A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data


Yining Wang, Yu-Xiang Wang, Aarti Singh ;
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1422-1431, 2015.


Subspace clustering groups data into several lowrank subspaces. In this paper, we propose a theoretical framework to analyze a popular optimization-based algorithm, Sparse Subspace Clustering (SSC), when the data dimension is compressed via some random projection algorithms. We show SSC provably succeeds if the random projection is a subspace embedding, which includes random Gaussian projection, uniform row sampling, FJLT, sketching, etc. Our analysis applies to the most general deterministic setting and is able to handle both adversarial and stochastic noise. It also results in the first algorithm for privacy-preserved subspace clustering.

Related Material