A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-Reduced Data
Abstract
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.
Cite
Text
Wang et al. "A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-Reduced Data." International Conference on Machine Learning, 2015.Markdown
[Wang et al. "A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-Reduced Data." International Conference on Machine Learning, 2015.](https://mlanthology.org/icml/2015/wang2015icml-deterministic/)BibTeX
@inproceedings{wang2015icml-deterministic,
title = {{A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-Reduced Data}},
author = {Wang, Yining and Wang, Yu-Xiang and Singh, Aarti},
booktitle = {International Conference on Machine Learning},
year = {2015},
pages = {1422-1431},
volume = {37},
url = {https://mlanthology.org/icml/2015/wang2015icml-deterministic/}
}