A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data
Yining Wang, Yu-Xiang Wang, Aarti Singh · 2015
Subspace clustering groups data into several low-rank 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 algo-rithms. We show SSC provably succeeds if the random projection is a subspace embedding, which includes random Gaussian projection, uni-form 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 algo-rithm for privacy-preserved subspace clustering. 1.